代码随想录算法训练营第23期day43

算法训练营第23期day43"/>

代码随想录算法训练营第23期day43

目录

一、（leetcode 518）零钱兑换II

二、（leetcode 377）组合总和 Ⅳ

完全背包问题和01背包在描述上的区别是：完全背包中的物品可以被无限使用；在代码上的区别是：遍历顺序中都是从小到大遍历，需要注意内外层的嵌套顺序要根据题目适时调整。 

一、（leetcode 518）零钱兑换II

力扣题目链接

状态：查看思路后AC。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount+1, 0);dp[0] = 1;int len = coins.size();for(int i = 0; i < len; ++i){for(int j = coins[i]; j < amount+1; ++j){dp[j] += dp[j-coins[i]];}}return dp[amount];}
};

二、（leetcode 377）组合总和 Ⅳ

力扣题目链接

状态：Debug后AC。

与上一题的区别在于组合的顺序问题，允许[1, 1, 2]和[2, 1, 1]算作两种不同的组合。这种情况需要先遍历背包（j），再遍历物品（i），同时加入判断

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<double> dp(target+1, 0);dp[0] = 1;int len = nums.size();for(int j = 0; j < target+1; ++j){for(int i = 0; i < len; ++i){if(j-nums[i] >= 0){dp[j] += dp[j-nums[i]];}}}return int(dp[target]);}
};