爬楼梯完全背包版本

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m

输出描述

输出一个整数，表示爬到楼顶的方法数。

输入示例

3 2

输出示例

3

题目链接：https://kamacoder.com/problempage.php?pid=1067

文章讲解：https://programmercarl.com/0070.爬楼梯完全背包版本.html

思路

爬楼梯这个问题也可以映射为背包问题，因为每次选择都是选择爬一阶或者二阶

但是现在每次可以爬m个台阶，选择变多了，问有多少种不同的方法可以爬到楼顶呢？

其实是一个完全背包问题，

每次可做的选择，1，2，3，4，..，m阶是物品，楼顶是背包。

物品可重复使用---例如跳了1阶，还可以继续跳1阶。

问有多少种不同的方法其实是问有多少种方法恰好装满背包？

这时就和 组合总和IV 基本一致了

动规五部曲

1、dp数组及下标含义

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。

2.、递推公式

在目标和、组合总和、零钱兑换 这几道题在说过。求恰好装满背包有几种方法，一维dp使用的是dp[i] += dp[i - nums[j]];

那么本题题递推公式：dp[i]+=dp[i-j]

3、dp数组初始化

dp[i] = 1

4、确定遍历顺序

完全背包求排列，应该先背包再物品。

5、举例推导

代码实现

#include <iostream>
#include <vector>
int main() {
    int n, m;
    while (std::cin >> n >> m) {
        std::vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int j = 1; j <= n; j++) { // 遍历背包，因为背包容量为0得时候，方法只有一种即默认dp[0]
                                       // = 1，所以不用再重新计算。
            for (int i = 1; i <= m; i++) { // 遍历物品，物品i得重量就是i
            // 如果 j < i 说明从只要跳就一定会越过j阶，因为步子太大了，无论你是从那里起跳都会越过。
                if (j >= i)
                    dp[j] += dp[j - i];  //为了到达第 j 阶，我可以从第 j-1 阶跳 1 步，从第 j-2 阶跳 2 步，...，直到从第 j-m 阶跳 m 步
            }
        }
        std::cout << dp[n] << std::endl;
    }
    
    return 0;
}