背包问题二：衍生问题

最初的 01背包问题是求能取得的最大价值。

二维转移方程为：

dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]]

优化空间后的一组转移方程为：

dp[j] = max(dp[j], v[i]+dp[j-w[i])

伪代码：

dp = [0] * (W+1) # 初始价值为 0

for i in 0 to n:
  for j in W to w[i]:  # 逆序遍历
    dp[j] = max(dp[j], v[i]+dp[j-w[i]])

背包问题可衍生为：

来讨论这几个问题：

322. 零钱兑换

这是一个完全背包问题，每个硬币可以不限次数的拿。与 01 的转移方程不同在于第二层循环要顺序遍历（而不是逆序）

求最小个数，初始 dp[] 元素全为最大 float('inf')。而第 0 个物品可以把第 0 个背包装满，所用物品数量为 0，所以有 dp[0] = 0。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        dp = [ float('inf') ] * (amount+1)
        dp[0] = 0
        for i in range(len(coins)):
            for j in range(coins[i], amount+1, 1):
                dp[j] = min(dp[j], dp[j-coins[i]]+1)

        return dp[-1] if dp[-1] != float('inf') else -1

dp[j] = min(dp[j], dp[j-coins[i]]+1) 不难理解：

如果不取当前硬币不取，之前装满 j 的硬币数，记为 dp[j]
如果取当前硬币，j-cons[i] 装满花的硬币数 dp[j-coins[i]]，取当前硬币，所以要加 1

416. 分割等和子集

这个问题相当于：数组中每个元素的值是它们的重量，每个元素的价值是 1，背包能否装满

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        S = sum(nums)
        if S & 1: return False

        S >>= 1
        dp = [False] * (S+1)
        dp[0] = True
        for i in range(len(nums)):
            for j in range(S, nums[i]-1, -1):
                dp[j] = dp[j] or dp[j-nums[i]]
            if dp[S]:
                return True
        return False

能否装满是一个 True or False 问题，转移方案不能再用 max，而是 or ：

dp[j] = dp[j] or dp[j-nums[i]]

就是，如果不取当前元素就已经满了，或容量为 j-nums[i] 的背包满了（那么 j-nums[i] + nums[i] = j，当前就肯定满了）。

494. 目标和

这个问题相当于：背包容量为 W，恰好装满的方案总数。

dp[i][j] 表示前 i 个元素把容量为 j 的背包装满的方案数。初始时只有 0 个元素能把容量为 0 的背包装满，所以 dp[0] = 1。一组转移方程为：

dp[j] = sum(dp[j], dp[j-w[i]])

解释：

比如当前背包容量是 11，当前元素值是 5，那么：

dp[j] = 背包已装满，当前元素不拿的方案数 dp[j-w[i]] = 装满背包容量为 6 （11-5=6 ）的方案数所以 dp[j] = dp[j] + dp[j-w[i]]

meishaoming / blog