LeetCode 518 零钱兑换 II
🟡 中等
https://leetcode.cn/problems/coin-change-ii/description/
对于本层输入index 有选和不选，简单递归。
- 注意 一定要等index 到最后才能返回，中途不能返回。
class Solution {
public:
int sel_not(vector<int>& coins, int index,int cap){
// if(cap==0) return 1;
if(index==coins.size()){
if(cap==0) return 1;
return 0;
}
if(cap>=coins[index]){
return sel_not(coins,index+1,cap)+sel_not(coins,index,cap-coins[index]);
}else{
return sel_not(coins,index+1,cap);
}
}
int change(int amount, vector<int>& coins) {
return sel_not(coins,0,amount);
}
};
改为动态规划
内层循环本来是 0-amount，但是不满足if条件就什么也不做，因此直接将if 条件转到for循环上面。
class Solution {
public:
int sel_not(vector<int>& coins, int index, int cap) {
// if(cap==0) return 1;
if (index == coins.size()) {
if (cap == 0)
return 1;
return 0;
}
if (cap >= coins[index]) {
return sel_not(coins, index + 1, cap) +
sel_not(coins, index, cap - coins[index]);
} else {
return sel_not(coins, index + 1, cap);
}
}
int change(int amount, vector<int>& coins) {
int dp[amount + 1];
memset(dp, 0, sizeof dp);
dp[0] = 1;
for (int i = coins.size() - 1; i >= 0; i--) {
for (int j = coins[i]; j <=amount; j++) {
// if (j >= coins[i]) {
dp[j] = dp[j]+dp[j-coins[i]];
// }
}
}
// return sel_not(coins, 0, amount);
return dp[amount];
}
};