This is the 21st day of my participation in the First Challenge 2022

preface

  • Some love each other, some drive at night to watch the sea, someleetcodeYou can’t do the first one, so you can see,leetcodeThe problem has weight. Today we’re going to meet them

Title address

Climb the stairs

Subject to introduce

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

 

Example 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 + 2. 2Copy the code

Example 2:

Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top of the building. 1. 1 order + 1 order + 1 order 2. 1 order + 2 order 3Copy the code

Dynamic programming

Train of thought

  • We usef(x)f(x)To climb to the first positionxxThe number of steps, considering that the last step may be one step or two steps, we can list the following formula:
F (x)= F (x-1)+ F (x-2) F (x)= F (x-1)+ F (x-2)Copy the code

  • It means that the number of options for climbing up the xx step is the sum of the number of options for climbing up the X-1x −1 step and the number of options for climbing up the X-2x −2 step. This makes sense, since you can only climb one or two steps at a time, so f(x)f(x) can only be transferred from f(x-1)f(x−1) and F (x-2)f(x−2), and to count the total number of alternatives, we need to sum the contributions of these two terms.

  • So that’s the transition equation for dynamic programming, and now let’s talk about the boundary conditions. We started at level 0, so from level 0 to level 0 we can think of it as only one way, f(0)=1 f(0)=1; There is only one way to go from level 0 to level 1, which is to climb one level, f(1)= 1f(1)=1. These two as boundary conditions can continue to deduce the correct results of the nn order. F (2)= 2F (2)=2, f(3)= 3F (3)=3, f(4)= 5f(4)=5… We enumerate all these cases and find that the calculation is correct.

solution

/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
   const dp = [];
   dp[0] = 1;
   dp[1] = 1;
   for(let i = 2; i <= n; i++) {
       dp[i] = dp[i - 1] + dp[i - 2];
   }
   return dp[n];
};
Copy the code

Tip:

1 <= n <= 45
Copy the code

Write in the last

  • I hope you find it rewarding