力扣第518题-零钱兑换Ⅱ1.本题是经典的完全背包动态规划问题核心递推公式为dp[j] dp[j - coins[i]]即当前金额j的组合总数等于上一轮的组合数加上本轮减去该硬币金额的组合数。一定要记得令dp[0] 1在本题的意思为“金额为0时只有不选任何硬币这1种方案”。完整代码如下1. int change(int amount, int* coins, int coinsSize) { 2. // dp[j]凑成金额j的组合方案总数用unsigned long long防止数值溢出 3. unsigned long long dp[amount 1]; 4. memset(dp, 0, sizeof(dp)); 5. // 金额0不选任何硬币存在1种方案 6. dp[0] 1; 7. 8. // 完全背包硬币可无限选取外层遍历硬币种类 9. for (int i 0; i coinsSize; i){ 10. // 正序遍历金额允许重复使用当前硬币 11. for (int j coins[i]; j amount; j){ 12. dp[j] dp[j - coins[i]]; 13. } 14. } 15. 16. // 转换为int返回最终凑amount的方案数 17. return (int)dp[amount]; 18. }该算法时间复杂度为O(coinsSize * amount)空间复杂度为O(amount)。本题的提交测试算例需要使用unsigned long long才能通过否则会溢出。2.经过这一系列的题目训练后发现题目中如果要求方案数最值则递推公式就要使用fmax或fmin如果要求“恰好等于某个值”的方案数则递推公式就要使用累加。3.对于dp[0]的初始化取决于题目中的约束条件根据实际情况来判断当容量为0时应该初始化为多少。4.纯完全背包问题是求凑成背包最大价值是多少而本题是要求凑成总金额的物品组合个数所以两层for循环不能互换。1纯完全背包的定义给定背包容量物品有重量和价值求能装入的最大总价值。求极值根本不关心物品是以什么顺序放进去的它只关心最终这个子集能达到多大的数值。所以两层for循环可以互换。2本题的定义给定总金额求凑成总金额的硬币组合数。组合是无序的外层硬币种类、内层金额可以保证后加入的硬币永远排在先加入的硬币后面也就是说一定是先处理完之前的硬币才会去处理后来的硬币这样就能保证不会出现重复情况。如果互换了变成外层金额、内层硬币种类就会导致在每一步容量都会去重新审视所有的硬币最终就会算成有重复的排列数而不是组合数力扣第377题-组合总和Ⅳ1.本题是一道完全背包问题与以往题目不同的一点在于本题的组合包含顺序不同的重复情况也就是说必须令外层循环为target内层循环为数的种类。完整代码如下1. int combinationSum4(int* nums, int numsSize, int target) { 2. // dp[i]凑成总和 i 的组合排列总数ull防止大数溢出 3. unsigned long long dp[target 1]; 4. memset(dp, 0, sizeof(dp)); 5. dp[0] 1; // 和为0空排列1种方案 6. 7. // 先遍历容量总和再遍历数字 → 求排列顺序不同算不同解 8. for (int i 0; i target; i){ 9. for (int j 0; j numsSize; j){ 10. if (i nums[j]){ 11. dp[i] dp[i - nums[j]]; 12. } 13. } 14. } 15. 16. return (int)dp[target]; 17. }该算法时间复杂度为O(numsSize * target)空间复杂度为O(target)。2.交换for循环就能求重复情况这一结论是比较抽象的下面是ai根据本题给出的详细推演过程因为外层是容量每一次容量增加所有的硬币都会重新获得一次“站在队伍最后”的平等竞争机会这就是为什么它能完美穷举出所有不同排列的原因。3.如果target为0题目上并没有将空集列为答案理论上dp[0]应该初始化为0但实际上需要初始化为1。本题计算组合数需要一个“火种”否则后续的累加的结果将一直是0。4.可以将dp[0]的初始化进行一个总结1最终结果求方法数时恰好等于某个值的组合数因为递推公式中仅依靠dp数组中的元素来进行累加所以必须需要一个火种来启动此时就需要将dp[0]初始化为1。2最终结果求最值时放入背包的最大价值、不大于某个值的最大子集因为递推公式中都会用到fmax或者fmin且其中非自身元素的那一项都会额外加上一个常数价值val或者数量1可以依靠自身来启动所以将dp[0]初始化为0避免干扰后续累加的那个常数。