灵神基础算法精讲-18-学习笔记

0 - 1 背包和完全背包都是非常重要的 DP 模型，它们是 选或不选 这个思想的代表。

0 - 1 背包

先从回溯开始思考，考虑第 i 个物品是 选 还是 不选，不选的话容量不变，选的话容量变小，这样就确定了递归参数中的 i 和 c，它对应的子问题就是在剩余容量 为 c 的情况下，从前 i 个物品中能得到的最大价值和；如果不选，就递归到 dfs(i - 1, c)，表示在剩余容量为 c 时，从前 i - 1 个物品中得到的最大价值和；如果选，就递归到 dfs(i - 1, c - w[i]) + v[i]，表示在剩余容量为 c - w[i] 时，从前 i - 1 个物品中得到的最大价值和。最终对这两个取最大值就是 dfs(i, c) 的结果了。

def zero_one_knapsack(capacity: int, w: List[int], v: List[int]) -> int:
    n = len(w)
    
    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        if c < w[i]:
            return dfs(i - 1, c)
        return max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])
    return dfs(n - 1, capacity)

494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

思路

假设添加正号的数的和为 p，添加负号的数的和为所有数的和 s - p，则 p - (s - p) = target，2p = s + t，p = (s + t) / 2。那么问题就变成从 nums 中选择一些数字，使得它们的和恰好等于 (s + t) / 2 的方案数，注意 s + t 需要除以 2，那么 s + t 必须是一个偶数，并且由于 nums[i] 是非负数，所以无论怎么选都无法得到负数，那么 s + t 是不能为负数的。

经过上述转换之后，这题就变成选一些数，这些数的和恰好等于一个数的方案数了，这是 0 - 1 背包的常见变形。根据加法原理，需要把取最大值操作改成加法。

做法

记忆化搜索

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c == 0 else 0
            if c < nums[i]:
                return dfs(i - 1, c)
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])
        return dfs(n - 1, target)

时间复杂度就是 n 乘上最后算出的 target，空间复杂度同理。

递推

把 dfs 改成 f 数组，把递归改成循环。为了避免出现负数下标，可以把 f[i] 改成 f[i + 1]，f[i - 1] 改成 f[i]
dfs(i, c) = dfs(i - 1, c) + dfs(i - 1, c - w[i])

f[i][c] = f[i - 1][c] + f[i - 1][c - w[i]]

f[i + 1][c] = f[i][c] + f[i][c - w[i]]

二维数组

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        f = [[0] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 1

        for i, x in enumerate(nums):
            for c in range(target + 1):
                if c < x:
                    f[i + 1][c] = f[i][c]
                else:
                    f[i + 1][c] = f[i][c] + f[i][c - x]
        return f[-1][-1]

两个数组

每次把 f[i + 1] 算完之后，后面就不会用到 f[i] 了，也就是说，每时每刻只有两个数组中的元素在参与状态转移，那么就可以只用两个数组。比如把 f[1] 计算完之后，在计算 f[2] 的时候，直接把结果填到 f[0] 当中，计算 f[3] 的时候，f[1] 没用，直接把结果填到 f[1] 里面。代码实现：把所有的 i 和 i + 1 都模 2 就好了。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        f = [[0] * (target + 1) for _ in range(2)]
        f[0][0] = 1

        for i, x in enumerate(nums):
            for c in range(target + 1):
                if c < x:
                    f[(i + 1) % 2][c] = f[i % 2][c]
                else:
                    f[(i + 1) % 2][c] = f[i % 2][c] + f[i % 2][c - x]
        return f[n % 2][target]

一个数组

把递推式进行如下简化：

f[i + 1][c] = f[i][c] + f[i][c - w[i]]

f[c] = f[c] + f[c - w[i]]

从左到右算会把前面的覆盖掉，那就从右到左算。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        f = [0] * (target + 1)
        f[0] = 1

        for x in nums:
            for c in range(target, x - 1, -1):
                f[c] = f[c] + f[c - x]
        return f[target]

完全背包

把 0 - 1 背包中的 n 个物品改为 n 种物品，每种物品可以重复选，先用回溯思考。这里和 0 - 1 背包的回溯的区别在于选了一个物品之后，i 是不变的，表示可以继续选第 i 种物品，所以：

dfs(i, c) = max(dfs(i - 1, c), dfs(i, c - w[i]) + v[i])

def unbounded_knapsack(capacity: int, w: List[int], v: List[int]) -> int:
    n = len(w)
    
    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        if c < w[i]:
            return dfs(i - 1, c)
        return max(dfs(i - 1, c), dfs(i, c - w[i]) + v[i])
    return dfs(n - 1, capacity)

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路

需要从这些数字中选择一些数，恰好组成 amount，每个数可以重复选，问最少需要多少个数，如果无法做到，就返回 -1。

做法

记忆化搜索

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

        @cache
        def dfs(i, c):
            if i < 0:
                return 0 if c == 0 else inf
            if c < coins[i]:
                return dfs(i - 1, c)
            return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)
        ans = dfs(n - 1, amount)
        return ans if ans < inf else -1

二维数组

需要注意数组的初始值，根据递归的边界条件，当 i 等于 0，且 c 等于 0 的时候才是 0，其他的都是无穷大。

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

        f = [[inf] * (amount + 1) for _ in range(n + 1)]
        f[0][0] = 0

        for i, x in enumerate(coins):
            for c in range(amount + 1):
                if c < x:
                    f[i + 1][c] = f[i][c]
                else:
                    f[i + 1][c] = min(f[i][c], f[i + 1][c - x] + 1)
        ans = f[n][amount]
        return ans if ans < inf else -1

一个数组

对于完全背包，正序计算就是对的，因为在计算 f[i + 1] 的时候，从前面转移过来的也是 f[i + 1] 的值：

f[i + 1][c] = min(f[i][c], f[i + 1][c - w[i]] + v[i])

f[c] = min(f[c], f[c - w[i]] + v[i])

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

        f = [inf] * (amount + 1)
        f[0] = 0

        for x in coins:
            for c in range(x, amount + 1):
                f[c] = min(f[c], f[c - x] + 1)
        ans = f[amount]
        return ans if ans < inf else -1 

常见变形

求方案数，至多装 capacity

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 # 不需要判断 c == 0
            if c < nums[i]:
                return dfs(i - 1, c)
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])
        return dfs(n - 1, target)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        f = [1] * (target + 1) # 都初始化为 1

        for x in nums:
            for c in range(target, x - 1, -1):
                f[c] = f[c] + f[c - x]
        return f[target]

求方案数，至少装 capacity

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c <= 0 else 0 # 修改为 c <= 0
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])
        return dfs(n - 1, target)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        
        target //= 2
        n = len(nums)

        f = [0] * (target + 1)
        f[0] = 1

        for x in nums:
            for c in range(target, -1, -1): # 需要循环到 0
                f[c] = f[c] + f[max(c - x, 0)] # 表示把所有 c <= 0 的状态都记录到 f[0] 里面
        return f[target]

为什么0 - 1 背包在遍历时是倒序，完全背包在遍历时是正序？

DeepSeek的回答

这是一个非常经典且重要的动态规划问题。核心区别在于两种背包问题对物品选取次数的限制不同，这导致了状态转移时依赖的子状态不同，从而需要不同的遍历顺序来保证状态的正确更新。

核心思想

我们先理解动态规划数组 dp[j] 的含义：它表示在当前阶段（考虑完部分物品后），对于容量为 j 的背包，所能获得的最大价值。

• 正序遍历会覆盖并利用当前阶段已经更新的、较小的 j 的值。
• 倒序遍历会保留上一阶段（未考虑当前物品时）的、较小的 j 的值。

---

1. 0-1背包问题（每个物品最多选一次）

为什么倒序？

目标：确保在计算 dp[j] 时，所依赖的 dp[j - weight[i]] 是 “上一轮” 的值，即还没有考虑过当前物品 i 时的状态。这样才能保证每个物品只被加入一次。

举例说明：
假设有一个物品，重量 weight[i] = 2, 价值 value[i] = 5。
背包容量 j 从 0 到 5。

• 初始状态：dp = [0, 0, 0, 0, 0, 0]

• 如果错误地使用正序 (j 从 2 到 5)：

  • j = 2: dp[2] = max(dp[2], dp[0] + 5) = max(0, 0+5) = 5 -> 新的 dp[2] 变成了 5
  • j = 4: dp[4] = max(dp[4], dp[2] + 5) = max(0, 5+5) = 10 -> 这里错了！
  • 错误在于，计算 dp[4] 时，用到的 dp[2] 是 本轮刚刚更新过的值（已经包含了当前物品）。这相当于把重量为2的物品用了两次（一次在 dp[2]，一次在 dp[4]），这违反了0-1背包的规则。

• 正确使用倒序 (j 从 5 到 2)：

  • j = 5: dp[5] = max(dp[5], dp[3] + 5) = max(0, 0+5) = 5
  • j = 4: dp[4] = max(dp[4], dp[2] + 5) = max(0, 0+5) = 5
  • j = 3: dp[3] = max(dp[3], dp[1] + 5) = max(0, 0+5) = 5
  • j = 2: dp[2] = max(dp[2], dp[0] + 5) = max(0, 0+5) = 5
  • 最终状态：dp = [0, 0, 5, 5, 5, 5]
  • 为什么正确？因为当我们计算 dp[4] 时，dp[2] 还是初始的0（上一轮的值），我们还没有用当前物品去更新它。这样就保证了每个物品在每种容量下只被考虑加入一次。

结论：对于0-1背包，倒序遍历容量是为了保证每个物品只被使用一次。

---

2. 完全背包问题（每个物品可以选无限次）

为什么正序？

目标：允许在计算 dp[j] 时，所依赖的 dp[j - weight[i]] 是 “本轮” 已经更新过的值。这样，如果 dp[j - weight[i]] 已经选择了k个物品i，那么 dp[j] 就可以选择k+1个物品i，从而实现物品的重复选取。

举例说明：
同样，一个物品，重量 weight[i] = 2, 价值 value[i] = 5。

• 初始状态：dp = [0, 0, 0, 0, 0, 0]
• 正确使用正序 (j 从 2 到 5)：
  • j = 2: dp[2] = max(dp[2], dp[0] + 5) = max(0, 0+5) = 5 // 拿1个物品
  • j = 4: dp[4] = max(dp[4], dp[2] + 5) = max(0, 5+5) = 10 // 拿2个物品
  • j = 6 (如果有): dp[6] = max(dp[6], dp[4] + 5) = max(0, 10+5) = 15 // 拿3个物品
  • 这正是我们想要的！在计算 dp[4] 时，我们用的 dp[2] 是5，这表示“在容量为2的背包里已经放了一个物品i，现在容量为4，我可以再放一个物品i”，从而实现了重复选取。

结论：对于完全背包，正序遍历容量是为了允许物品被多次选取。

---

总结与类比

特征	0-1背包	完全背包
物品限制	每个物品最多选1次	每个物品可以选无限次
遍历顺序	倒序 (j 从大到小)	正序 (j 从小到大)
原因	防止同一物品被重复计入	允许同一物品被重复计入
依赖的子状态	上一轮（未考虑本物品）的状态	本轮（已考虑本物品）的状态
核心思想	保护上一轮的状态不被覆盖	利用本轮已更新的状态

你可以这样记忆：

• 0-1背包是“保守派”：它小心翼翼地回头看，只用“过去”的经验，绝不重复今天的收获。
• 完全背包是“激进派”：它大胆地用“现在”已经创造的成果，去创造更大的成果，允许重复利用。