518. 零钱兑换 II
真是不太明白
class Solution {
public:
int change(int amount, vector<int>& coins) {
int coin_size = coins.size();
vector<int> dp(amount+1,0);
dp[0] = 1;
for(int i=0; i<coin_size; i++){
for(int j=coins[i]; j<=amount; j++){
dp[j] = dp[j] + dp[j-coins[i]];
}
}
return dp[amount];
}
};
后续：要想保证每个钱只使用一次，那么久只能把coin的遍历放在外面，然后里面的循环是一遍遍的算用当前的钱的组合有多少种。
377. 组合总和 Ⅳ
也是抄的。自己写的for loop想了半天内外循环，还是写反了。
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] + dp[i-nums[j]];
}
}
return dp[target];
}
};
后续：这道题也明白一些了。因为这道题不在乎用重复的数组成其中的一组答案。所以就可以将遍历数组放进能循环，每个数挨个的来算能不能组成当前的i（也就是未来即将要成为target） 的值。如果可以就把上一组外循环所得的当前dp[i]的值与i-当前数值所得到的组合书加在一起，就是目前能得到的值了。
