题目1： 518. 零钱兑换 II
算法思路： 背包问题，只是每个元素都可以取无数次。
代码：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int m = coins.size();
int n = amount;
vector<vector<unsigned int>> dp(m, vector<unsigned int>(n + 1));
dp[0][0] = 1;
for(int j = coins[0]; j <= n; j += coins[0]) {
dp[0][j] = 1;
}
for(int i = 1; i < m; i++) {
for(int j = 0; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
for(int k = j - coins[i]; k >= 0; k -= coins[i]) {
dp[i][j] += dp[i-1][k];
}
}
}
return dp[m - 1][n];
}
};
题目2: 377. 组合总和 Ⅳ
抄一下代码
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];
}
};
