70. Stair Climbing Advanced Edition

Refer to Code Caprice
70. Climbing stairs

This question is a partial modification of the original question:
Let's say you're climbing stairs.You need n steps to get to the top of the building.
Each time you can climb 1 or 2…n steps.How many different ways can you get to the top of a building?

dp array meaning:
dp[i]: There are dp[i] ways to climb to the top of the building with i steps.

Recursive formula:
dp[i] += dp[i -j];

Initialization:
dp[0] must be 1, dp[0] is the basis of all values ​​in the recursion, if dp[0] is 0, other values ​​are 0.

Traversal order:
This is a complete knapsack, so it is a sequential traversal. Through analysis, we can see that the sequence in this dp is an arrangement, so pay attention to the order in which the two for loops are nested

If the number of combinations is sought, the outer for loop traverses the items, and the inner for loops through the backpack
If the number of permutations is sought, the outer for loop traverses the backpack, and the inner for loop traverses the items
Convert the title:
One step, one step, two steps, etc., and then the whole process is, how many steps are taken each time and then to the top of the building.
Think of it this way: the number of steps that can be taken is an array, and the value from the array (each element can be taken repeatedly) is the number of steps required to go up to the top of the building.
At this point, it is clear that this is a complete knapsack problem.

class Solution {public:int climbStairs(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i++) { // Traverse the backpackfor (int j = 1; j <= m; j++) { // Traverse itemsif (i - j >= 0) dp[span>i] += dp[i - j];}}return dp[n];}};

The m in the code means that you can climb 1~m steps, and changing m to 2 in the code is the code for this question 70. Climbing stairs can be AC.