代码随想录算法训练营day46 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ

本文主要是介绍代码随想录算法训练营day46 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

完全背包

完全背包相对于01背包来说物品有无限个

代码的不同主要体现在遍历顺序上， 完全背包的背包重量不需要倒序遍历，因为物品有无限个，可以被无限添加；并且因为背包重量正序遍历，后续的值依赖于前面的值，因此背包和物品的内外层遍历也没有特定顺序

下面以物品外层循环，背包容量内层循环为例

def test_CompletePack(weight, value, bagWeight):dp = [0] * (bagWeight + 1)for i in range(len(weight)):  # 遍历物品for j in range(weight[i], bagWeight + 1):  # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])return dp[bagWeight]if __name__ == "__main__":weight = [1, 3, 4]value = [15, 20, 30]bagWeight = 4result = test_CompletePack(weight, value, bagWeight)print(result)

518. 零钱兑换 II

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

动态规划五部曲：

1. 确认dp数组以及下标的含义：dp[j]表示凑成金额j有dp[j]种不同的方式
2. 确认递推公式：dp[j] += dp[j-weight[i]]
3. dp数组的初始化：dp[0] = 1
4. 确认遍历顺序：物品在外，背包容量在内正序遍历
5. 举例推导dp数组：

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):dp[j] += dp[j - coin]return dp[amount]

377. 组合总和 Ⅳ

1. 确定dp数组以及下标的含义：dp[j]代表总和为j的排列个数为dp[j]
2. 确定递推公式：dp[j] += dp[j-nums[i]]
3. 数组的初始化：dp[0] = 1
4. 确定遍历顺序：因为是求排列，不同顺序算不同结果，因此背包重量在外层循环，物品在内层循环
5. 举例推导dp数组：

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

这篇关于代码随想录算法训练营day46 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---