- 这是一道与上一题几乎一样的题目
- 不同点是在上一题是组合,这道题是排列
- 所以就要用先循环背包,内循环为物品来实现排列效果
- 总结:
- 对纯完全背包,求装满这个背包的最大价值,或者问能不能装满这个背包,那么两层for循环不分内外,谁在外层或内层都没有影响
- 如果问题变为装满这个背包有多少种方法,求
- 扩展:这道题与爬楼梯类似
- 爬楼梯是有两种方式,一层或二层,如果有
m
层呢,就相当于本题集合中元素有{1, 2, 3,..., m}
,代表了m
种爬楼梯方法(值代表一次可以爬的层数),问到达楼顶有多少种方法,这其中的楼顶层数就类似于本题中的target
(万万没想到这还能联系上)
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int j = 0; j < nums.size(); j++) {
if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};
- 测试用例有两个数相加超过int的数据,所以需要在if里加上
dp[i] < INT_MAX - dp[i - num]
- 汇总