本质是爬楼梯,相当于每次往上爬 nums[i]步
本题和爬楼梯是一个思路,只不过我们每次从 nums 中选一个数,作为往上爬的台阶数,问爬 target 个台阶有多少种方案。爬楼梯那题可以看作 nums=[1,2],因为每次只能爬 1 个或 2 个台阶。
代码如下:
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1; // 参考爬楼梯
for (int i = 1; i <= target; i++) {
for (int x : nums) {
if (x <= i) {
dp[i] += dp[i - x];
}
}
}
return dp[target];
}
}