Dynamic planning -- multi-step stair climbing (advanced version of stair climbing)

Step up the stairs

Title Description 1

Suppose you're climbing the stairs . need n You can reach the top of the building .

Every time you climb 1 or 2 A stair ,3 A stair …, until m A stair . How many different ways can you climb to the top of the building ？

Be careful ： Given n Is a positive integer .

Example 1：

 Input ： 2 

 Output ： 2 

 explain ：  There are two ways to climb to the top .

1  rank  + 1  rank 
2  rank 

Example 2：

 Input ： 3 

 Output ： 3 
 explain ：  There are three ways to climb to the top .

1  rank  + 1  rank  + 1  rank 
1  rank  + 2  rank 
2  rank  + 1  rank 

1 rank ,2 rank ,… m Order is the object , The roof is the backpack .

Each step can be reused , For example, I jumped 1 rank , You can continue to jump 1 rank .

There are several ways to jump to the top of a building. In fact, there are several ways to fill a backpack .

It's a complete knapsack problem

analysis ：

1. determine dp Array meaning ： Climb to i There are... On the top of the building with steps dp[i] Methods 
2. Determine the recurrence formula ： The recurrence formula of several methods to solve knapsack problem is generally dp[i] += dp[i-nums[i]];
 The recurrence formula of this problem is ：dp[i] += dp[i-j]
3. initialization dp Array ： There is a recursive formula that shows dp[0] = 1 because dp[0] It is the basis of all numerical values in the recursive process , If dp[0] by 0, Then other values are 0
4. Establish traversal order ： This question is about permutation , That is, the outer layer traverses the knapsack , Inner traversal item . If it is a combination problem , Then the outer layer is traversal items , The inner layer is traversal knapsack 
5. Give an example to deduce dp Array 

Code

#include<iostream>
#include<vector>
using namespace std;` Insert a code chip here `
class Solution{
    
	public:
		int climbStairs(int n, int m) {
    
			vector<int> dp(n+1);
			dp[0] = 1;
			for (int i = 1; i <= n; i++) {
    // Traverse the backpack 
				for (int j = 1; j <= m; j++) {
    // Traverse the items 
					if (i-j >= 0) dp[i] += dp[i-j];
				}
			}
			return dp[n];
		}
};
int main() {
    
	int n, m;
	cin>>n>>m;
	Solution Q;
	cout<<Q.climbStairs(n,m);
}