leetcode(4)背包系列题目

背包递推公式

1. 问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

   • 322.零钱兑换

   考过没做出来
   初始化凑成每个金额都使用面额为1的硬币，则最多需要amount个硬币，因此初始化为amount + 1

   class Solution:
       def coinChange(self, coins: List[int], amount: int) -> int:
           dp = [amount + 1] * (amount + 1) # 都是amount + 1
           dp[0] = 0
           for c in coins:
               for j in range(c, amount + 1):
                   dp[j] = min(dp[j], dp[j - c] + 1)
           return dp[amount] if dp[amount] < amount + 1 else -1 # 如果<就说明是由coins里面组成的
   

   • 279.完全平方数

   考过没做出来
   就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

   class Solution:
       def numSquares(self, n: int) -> int:       
           dp = [10**4] * (n + 1)  # 初始化背包装每个重量时的最多物品个数
           dp[0] = 0  # 第0个开始
           nums = []
           i = 1
           while i*i <= n:  # 初始化每个物品的重量
               nums.append(i*i)
               i += 1
           for num in nums:
               for j in range(num,n + 1):
                   dp[j] = min(dp[j], dp[j - num] + 1)
           return dp[-1]
   

总结：动态规划-我的一生之敌...(不是)转移方程一定要想清楚！！！

一、01背包问题

如果使用二维dp数组，先遍历物品还是先遍历背包重量都可以，且两层循环都是正序遍历！
如果使用一维dp数组，只能是物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

a.内层循环遍历顺序

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

因为倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

那么问题又来了，为什么二维dp数组历的时候不用倒序呢？

因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

b.两个嵌套for循环的顺序

只能是物品遍历的for循环放在外层，遍历背包的for循环放在内层。

因为一维dp的写法，背包容量一定是要倒序遍历，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

二、完全背包问题

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

a.内层循环遍历顺序

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大正序遍历

b.两个嵌套for循环的顺序

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

三、求装满背包有几种方法

初始化为：dp[0]=0，而前面是：dp[0]=1
递推公式：dp[j] += dp[j - nums[i]]

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
• 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
• 如果求最小数，那么两层for循环的先后顺序就无所谓了。

求组合数：动态规划：518.零钱兑换II
求排列数：动态规划：377. 组合总和 Ⅳ 、动态规划：70. 爬楼梯进阶版（完全背包）
求最小数：动态规划：322. 零钱兑换 、动态规划：279.完全平方数 (递推公式为：dp[j]=min(dp[j],dp[j - nums[i]]+ 1))

四、多重背包问题

多重背包介于完全背包和01背包问题之间，即每种物品的个数是指定的。

参考资料：
背包问题总结篇
一篇文章吃透背包问题！
一文搞懂完全背包问题