Topic describes

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 of the building.

  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 of the building.

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

Source: LeetCode link: leetcode-cn.com/problems/cl… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Do you need to climb one or two steps to complete n steps?

  • Dynamic programming for complete knapsack problem;
  • Determine the meaning of DP: DP [J] indicates that j steps have N ways to reach the roof;
  • Determine the dp recursion formula:
    • The number of ways to climb the NTH stair is equal to the sum of the two parts
    • Number of ways to climb n-1 stairs. Because it takes one more step to get to the NTH
    • Number of ways to get up n minus 2 stairs, because it takes 2 more steps to get to the NTH
    • So the recursive formula: dp[j]= DP [J-1]+ DP [J-2]
  • Dp array initialization:
    • dp[0]=0; dp[1]=1; dp[2]=2; Actual meaning n>0, only as the basis of recursion; Other non-zero subscripts are initialized to 0;
  • Traversal order: traversal capacity N; Walk through the object again;

code

/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function(n) {

    if(n<=2) {return n;
    }
    let dp=new Array(n+1).fill(0);
    dp[0] =0; dp[1] =1; dp[2] =2
    // Items 1 and 2 can be used multiple times to fill containers of capacity N;
    Steps =[1,2];
    for(let j=3; j<=n; j++){ dp[j]=dp[j-1]+dp[j-2]}return dp[n]
   
};
Copy the code

Step up the stairs

Topic describes

M steps at a time? Suppose you’re climbing stairs. It takes n steps to get to the top.

Steps [I]; 0<i<m; Steps [m] 1, 2, 3, 4, 5,…. How many different ways can you climb to the top?

Note: given n is a positive integer. m<n;

Their thinking

  • Dynamic programming for complete knapsack problem;

  • Determine the meaning of DP: DP [J] indicates that j steps have N ways to reach the roof;

  • Determine the dp recursion formula:

    • Number of ways to climb the NTH stair
    • dp[j]=dp[j]+dp[j-steps[i]]

  • Dp array initialization:

    • dp[0]=1; Actual meaning n>0, only as the basis of recursion; Other non-zero subscripts are initialized to 0;

  • Traversal order: at this point, the problem is transformed into a complete knapsack 🎒 problem arrangement solution problem:

    Refer to full backpack at 🎒 question 377

conclusion

In seeking to fill a backpack 🎒 the key to the order of problems lies in:

If you take the number of combinations it’s the outer for loop going through the item, the inner for loop going through the backpack. If you take the number of permutations, it’s the outer layer for traverses the backpack, and the inner layer for loops through the items.

code

/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function(steps,n) {

    let dp=new Array(n+1).fill(0);
    dp[0] =1
    // You can repeat with steps[I] several times to fill a container of size N;
    for(let j=1; j<=n; j++){for(let i=0; i<steps.length; i++>){if(j-steps[i]>=0){
                 dp[j]+=dp[j-steps[i]]   
            }
        }

    }
    return dp[n]
   
};
Copy the code

The following code is completely AC:

So this problem can be completely solved by using the full backpack 🎒 problem:

/** * @param {number} n * @return {number} */ var climbStairs = function(n) { let dp=new Array(n+1).fill(0); Dp [0]=1 const steps=[1,2] // Items 1 and 2 can be used multiple times to fill containers of capacity N; for(let j=1; j<=n; J++){// for(let I =0; i<steps.length; I++){// iterate over items; If (j - steps [I] > = 0) {/ / current capacity greater than the current items dp [j] + = dp [j - steps [I]]}}} return dp [n]};Copy the code

Full backpack 🎒 problem

【 Review old and learn new 】322. ChangeAnimation demonstration – minimum solution of complete knapsack problem – Implementation of dynamic programming

【 Review old and learn new 】518. Change IICombinatorial solution of complete knapsack problem – Implementation of dynamic programming

【 Review old and learn new 】377. Sum of combinations ⅳPermutation solution of complete knapsack problem – Implementation of dynamic programming

01 Backpack 🎒 problem

【 Review old and learn new 】474. One and zero01 knapsack 🎒 problem maximum solution – dynamic programming implementation

【 Review old and learn new 】494. The target andExpression into 01 knapsack 🎒 problem – dynamic programming implementation

【 Review old and learn new 】1049. The weight of the last stone IIMinimum weight conversion to 01 knapsack 🎒 problem maximum solution – dynamic programming implementation

【 Review old and learn new 】416. Segmentation and subsets01 knapsack 🎒 problem existence solution – dynamic programming implementation