算法D44 | 动态规划6 | 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

力扣上没有纯粹的完全背包的题目，所以大家看本篇了解一下完全背包的理论

后面的两道题目，都是完全背包的应用，做做感受一下

完全背包

视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？_哔哩哔哩_bilibili

https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html

518.零钱兑换II

视频讲解：动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili

代码随想录

Python:

518和377两个题适合一起品一品，两层forloop的顺序对于结果是由影响的，如果先遍历物品后遍历背包，结果是组合，即518题；反之，如果先遍历背包后遍历物品，结果是排列，即377题。

class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount+1)dp[0] = 1for coin in coins:for j in range(coin, amount+1, 1):dp[j] += dp[j-coin]return dp[amount]

C++:

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

377.组合总和Ⅳ

视频讲解：动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV_哔哩哔哩_bilibili

代码随想录

Python:

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * (target+1)dp[0] = 1for j in range(1, target+1):for num in nums:if num>j: continuedp[j] += dp[j-num]return dp[target]

C++:

C++要注意处理加法溢出的情况。

class Solution {public:int combinationSum4(vector& nums, int target) {vector dp(target+1, 0);dp[0] = 1;for (int j=1; j j || dp[j]>=INT_MAX-dp[j-num]) continue;dp[j] += dp[j-num];}}return dp[target];}};