代码随想录背包问题完结

322. 零钱兑换

视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili

代码随想录 

该题在递推公式部分和474.一和零一样，求装多少个

不同在于

1. 该题是完全背包，可以重复使用同一个物品
2. 所以要求用最少的物品装满，这就要求dp数组初始化时初值应该尽量大，且dp[0] = 0

279.完全平方数

视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili

代码随想录 

该题在动态规划思路方面与上题一致，但是每个物品都是一个完全平方数这样才能符合题意

139.单词拆分

视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili

代码随想录

回溯，超出限制，

动态背包，个人觉得还是结合双指针法来理解比较舒服一些

多重背包

代码随想录

多重背包：n种物品，每个物品有多个

如果某一种物品有m个，就把他们当作m种属性相同的物品，这样就转化为01背包了