[Dynamic Programming]: 509. Fibonacci numbers, 70. Climbing stairs, 746. Climbing stairs with minimum cost

Tips: Live hard and have a happy day

Article directory

509. Fibonacci numbers
- Problem-solving ideas
- Problems encountered
- Code
- Summary of the question
70. Climb the stairs
- Problem-solving ideas
- Problems encountered
- Code
- Summary of the question
746. Climb the stairs with minimum cost
- Problem-solving ideas
- Problems encountered
- Code
- Summary of the question
Today’s experience

509. Fibonacci numbers

Question link: 509. Fibonacci numbers

Problem-solving ideas

Five steps of dynamic rules:

Determine the meaning of the dp array and the subscripts: dp[i] is defined as: the Fibonacci value of the i-th number is dp[i]
Determine the recursion formula: The question has given the recursion formula directly: state transition equation dp[i] = dp[i – 1] + dp[i – 2];
How to initialize the dp array: How to initialize is also given directly in the question, dp[0] = 0; dp[1] = 1;
Determine the traversal order: It can be seen from the recursive formula dp[i] = dp[i – 1] + dp[i – 2]; that dp[i] depends on dp[i – 1] and dp[i – 2] , then the order of traversal must be from front to back.
Take an example to deduce the dp array: follow the recursive formula to deduce it. If you find that the result is wrong, print out the dp array.

Problems encountered

Traversal starts from 2, less than or equal to N
Finally, return an item in the maintained array

Code implementation

Dynamic programming

var fib = function(n) {<!-- -->
    //Determine the meaning of the dp array and subscripts
    //dp[i] means that the value of the i-th position is dp[i]
    //How to initialize the dp array
    let dp = [0,1]
    //Determine the traversal order: traverse from front to back
    for(let i=2;i<=n;i + + ){<!-- -->
      //Determine the recursion formula
      dp[i] = dp[i-1] + dp[i-2]
    }
    //Example to derive dp array: and print the result
    console.log(dp)
    return dp[n]
};

Question summary

This question generally uses a recursive method, but it is also an introductory question to dynamic programming because the five steps of dynamic programming are very clear.
There are still areas that can be optimized in the above dynamic programming method. We only need to maintain two values and do not need to record the entire sequence.

var fib = function(n) {
  // In the dynamic state transfer, the current result only depends on the results of the first two elements, so only two variables replace the dp array to record the state process. Reduce space complexity to O(1)
    if(n===0)return 0
    if(n===1)return 1
    let pre0 = 0
    let pre1 = 1
    let sum = 0
    for(let i=1; i<=n; i + + ){
      sum = pre0 + pre1
      pre0 = pre1
      pre1 = sum
      console.log(pre0)
    }
    return pre0
};

70. Climbing stairs

Question link: 70. Climbing stairs

Problem-solving ideas

There is one way to climb the stairs to the first floor, and there are two ways to climb the stairs to the second floor.
Then take two more steps on the first flight of stairs to reach the third floor, and one more step on the second flight of stairs to reach the third floor.
So the state of the stairs to the third floor can be deduced from the state of the stairs to the second floor and the state of the stairs to the first floor, then you can think of dynamic programming.
Five steps of dynamic rules:

Determine the meaning of the dp array and subscripts: dp[i]: There are dp[i] ways to climb to the i-th floor of stairs
Determine the recursion formula: First, it is dp[i – 1]. There are dp[i – 1] ways to go up the stairs i-1, then wouldn’t it be dp[i] to jump one step at a time? There is also dp[i – 2]. There are dp[i – 2] ways to go up the i-2 stairs. Then jumping two steps in one step is dp[i]. Then dp[i] is the sum of dp[i – 1] and dp[i – 2]! So dp[i] = dp[i – 1] + dp[i – 2].
How to initialize the dp array: The question says that n is a positive integer, but the question does not say that n is 0 at all. It does not consider how to initialize dp[0], only initialize dp[1] = 1, dp[2] = 2, and then start recursively from i = 3, so as to comply with the definition of dp[i].
Determine the traversal order: It can be seen from the recursive formula dp[i] = dp[i – 1] + dp[i – 2]; that the traversal order must be traversed from front to back.
Take an example to derive the dp array: If there is a problem with the code, print out the dp table

Problems encountered

Although during initialization, dp[1] = 1, dp[2] = 2, in actual development, adding data to the array starts from dp[1], so the final return result is dp[n-1 ]

Code implementation

dynamic programming

var climbStairs = function(n) {<!-- -->
  //dp[i] is the number of ways to climb to the top of the i-th staircase
  // dp[i] = dp[i - 1] + dp[i - 2]
  let dp = [1,2]
  //Start from the third step
  for(let i = 2; i <= n; i + + ){<!-- -->
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n-1]
};

Question summary

This question is basically consistent with the Fibonacci sequence, but the recursive formula dp[i] = dp[i – 1] + dp[i – 2] is not directly reflected in the question.
This question can be further deepened, that is, one step at a time, two steps, three steps, until there are m steps. How many ways are there to climb to the top of n steps? You can think deeply about it.

746. Climb the stairs with minimum cost

Question link: 746. Climb the stairs with minimum cost

Problem-solving ideas

Five steps of dynamic rules:

Determine the meaning of the dp array and subscripts: When using dynamic programming, you need an array to record the status. This question only requires a one-dimensional array dp[i]. The definition of dp[i]: The minimum physical effort required to reach the i-th step is dp[i].
Determine the recursion formula: There are two ways to get dp[i], one is dp[i-1] and the other is dp[i-2]. It costs dp[i – 1] + cost[i – 1] to jump from dp[i – 1] to dp[i]. It costs dp[i – 2] + cost[i – 2] to jump from dp[i – 2] to dp[i]. So should we choose to jump from dp[i – 1] or from dp[i – 2]? The smallest one must be chosen, so dp[i] = min(dp[i – 1] + cost[i – 1], dp[i – 2] + cost[i – 2]);
How to initialize the dp array: The title description clearly states “You can choose to start climbing the stairs from the step with subscript 0 or subscript 1.” In other words, it does not cost to reach the 0th step, but starting from the 0th step If you jump up the stairs, you need to spend cost[0]. So initialize dp[0] = 0, dp[1] = 0;
Determine the traversal order: Because it is a simulated step, and dp[i] is derived from dp[i-1]dp[i-2], it is enough to traverse the cost array from front to back.
Take an example to derive the dp array: If there is a problem with the code, print out the dp table

Problems encountered

The final return result is dp[cost.length]

Code implementation

dynamic programming

var minCostClimbingStairs = function(cost) {<!-- -->
  //Definition of dp[i]: The minimum physical effort required to reach the i-th step is dp[i].
  //How to initialize the dp array
  let dp = [0,0]
  for(let i = 2; i <= cost.length; i + + ){<!-- -->
    //There are two ways to get dp[i], one is dp[i-1] and the other is dp[i-2]
    //dp[i - 1] jumps to dp[i] at a cost of dp[i - 1] + cost[i - 1]
    //dp[i - 2] Jumping to dp[i] costs dp[i - 2] + cost[i - 2]
    //The smallest one must be chosen, so dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])
  }
  return dp[cost.length]
};

Question summary

The problem of climbing stairs has been optimized and made more difficult.

Today’s experience

Today is my first contact with dynamic programming. I will deepen my understanding step by step according to the difficulty of the topic.