0070.爬楼梯完全背包版本
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
# 70. 爬楼梯（进阶版） [卡码网：57. 爬楼梯](https://kamacoder.com/problempage.php?pid=1067) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 输入描述：输入共一行，包含两个正整数，分别表示n, m 输出描述：输出一个整数，表示爬到楼顶的方法数。 输入示例：3 2 输出示例：3 提示： 当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。 此时你有三种方法可以爬到楼顶。 * 1 阶 + 1 阶 + 1 阶段 * 1 阶 + 2 阶 * 2 阶 + 1 阶 ## 思路 之前讲这道题目的时候，因为还没有讲背包问题，所以就只是讲了一下爬楼梯最直接的动规方法（斐波那契）。 **这次终于讲到了背包问题，我选择带录友们再爬一次楼梯！** 这道题目 我们在[动态规划：爬楼梯](https://programmercarl.com/0070.爬楼梯.html) 中已经讲过一次了，这次我又给本题加点料，力扣上没有原题，所以可以在卡码网[57. 爬楼梯](https://kamacoder.com/problempage.php?pid=1067)上来刷这道题目。 我们之前做的 爬楼梯 是只能至多爬两个台阶。 这次**改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？** 这又有难度了，这其实是一个完全背包问题。 1阶，2阶，.... m阶就是物品，楼顶就是背包。 每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。 问跳到楼顶有几种方法其实就是问装满背包有几种方法。 **此时大家应该发现这就是一个完全背包问题了！** 和昨天的题目[动态规划：377. 组合总和 Ⅳ](https://programmercarl.com/0377.组合总和Ⅳ.html)基本就是一道题了。 动规五部曲分析如下： 1. 确定dp数组以及下标的含义 **dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法**。 2. 确定递推公式 在[动态规划：494.目标和](https://programmercarl.com/0494.目标和.html) 、 [动态规划：518.零钱兑换II](https://programmercarl.com/0518.零钱兑换II.html)、[动态规划：377. 组合总和 Ⅳ](https://programmercarl.com/0377.组合总和Ⅳ.html)中我们都讲过了，求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]]; 本题呢，dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j] 那么递推公式为：dp[i] += dp[i - j] 3. dp数组如何初始化 既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。 下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果 4. 确定遍历顺序 这是背包里求排列问题，即：**1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！** 所以需将target放在外循环，将nums放在内循环。 每一步可以走多次，这是完全背包，内循环需要从前向后遍历。 5. 举例来推导dp数组 介于本题和[动态规划：377. 组合总和 Ⅳ](https://programmercarl.com/0377.组合总和Ⅳ.html)几乎是一样的，这里我就不再重复举例了。 以上分析完毕，C++代码如下：#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
while (cin >> n >> m) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) { // 遍历背包
for (int j = 1; j <= m; j++) { // 遍历物品
if (i - j >= 0) dp[i] += dp[i - j];
}
}
cout << dp[n] << endl;
}
}
import java.util.Scanner;
class climbStairs{
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
int m, n;
while (sc.hasNextInt()) {
// 从键盘输入参数，中间用空格隔开
n = sc.nextInt();
m = sc.nextInt();
// 求排列问题，先遍历背包再遍历物品
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= m; i++) {
if (j - i >= 0) dp[j] += dp[j - i];
}
}
System.out.println(dp[n]);
}
}
}
