背包问题 - 爬楼梯进阶版
背包问题 - 爬楼梯进阶版
假设你正在爬楼梯。需要 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 阶
分析
这其实是一个完全背包问题。
1 阶，2 阶，.... m 阶就是物品，到楼顶的台阶数就是背包的容量。每一阶可以重复使用，例如跳了 1 阶，还可以继续跳 1 阶。就是完全背包，问跳到楼顶有几种方法其实就是问装满背包有几种方法。
这其实是一个完全背包问题。
holy shit,真的是个天才般的思路。
然后，就跟 377. 组合总和 Ⅳ 一模一样了。
解题
public int combinationSum4(int m, int n) {
int[] dp = new int[n+1];
dp[0]=1;
for(int j=0;j<target+1;j++){
for(int i=0;i<m;i++){
// (i+1) 对应 nums[i]
if(j>=(i+1)]){
dp[j]=dp[j]+dp[j-(i+1)];
}
}
}
return dp[n];
}