Nuggets team number online, help you Offer impromptu! Click for details

I. Title Description:

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?

Note: given n is a positive integer.

Example 1:

Input: 2 Output: 2

Explanation: There are two ways to climb to the top.

  1. 1 order plus 1 order
  2. 2 order

Example 2:

Input: 3 Output: 3

Explanation: There are three ways to climb to the top.

  1. 1 order plus 1 order plus 1 order
  2. 1 order plus 2 order
  3. 2 order plus 1 order

Title link: leetcode-cn.com/problems/cl…

Ii. Analysis of Ideas:

So let’s think about the method that goes up to order n, the sum of the method that goes up to order N minus 1 and the method that goes up to order N minus 2, which is f(n) = f(n-1) + f(n-2).

Iii. AC Code:

var climbStairs = function(n) { let f = [] f[1] = 1 f[2] = 2 for(let i=3; i<=n; i++){ f[i] = f[i-1] + f[i-2] } return f[n] };Copy the code

Iv. Summary:

It is important to note that I starts at 3, because the problem states that n is a positive integer, so there is no case where n is 0, that is, f[2] = f[1] + f[0] does not exist; Then there is the case where f[1] and f[2] need to be initialized first.

Also, for step N, there are two ways to jump, so the formula is f(n)= F (n-1)+f(n-2). So why isn’t f(n)=1+f(n-1)+2+f(n-2)?

Because what is asked here is the jump method. In the idea of dynamic programming or recursion, there are only two jump methods for the NTH step, one is to jump up from the n-1 step, and the other is to jump up from the n-2 step directly. The “one-step” and “two-step” here correspond to the jump method given by the problem stem respectively. So it’s going to be 1f of n minus 1 plus 1f of n minus 2. The two 1s in front represent the number of methods from n-1, n-2 to n, respectively, and the f(n-1) in the back represents the jump method to reach the step F (n-1).

To put it mathematically, now from A to B to C, there are A ways to go from A to B, and there are B ways to go from B to C, so there are ab ways to go from A to C. Any of the ways A goes to B and any of the ways B goes to C can be combined into A way A goes to C, and that’s ab.

This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions