DP

1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

• DP 状态： dp[i] 表示爬到第 i 阶楼梯的方法数。
• 状态转移方程： 爬到第 i 阶，可以从 i-1 阶爬 1 步上来，也可以从 i-2 阶爬 2 步上来。所以 dp[i] = dp[i-1] + dp[i-2]。
• 初始状态： dp[0] = 1 (到达第 0 阶，视为一种方法)，dp[1] = 1 (到达第 1 阶，只有一种方法)。
• 遍历顺序： 从 i = 2 到 n 递增。

2. 最长公共子序列（Longest Common Subsequence, LCS）

给定两个字符串 S1 和 S2，找到这两个字符串的最长公共子序列的长度。子序列不要求连续。

• DP 状态： dp[i][j] 表示字符串 S1 的前 i 个字符和字符串 S2 的前 j 个字符的最长公共子序列的长度。
• 状态转移方程：
  • 如果 S1[i−1]==S2[j−1] （当前字符相等），那么 dp[i][j] = dp[i-1][j-1] + 1。
  • 如果 S1[i−1]!=S2[j−1] （当前字符不相等），那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (取两者中较大的)。
• 初始状态： dp[0][j] = 0 (S1 为空)，dp[i][0] = 0 (S2 为空)。
• 遍历顺序： 外层循环 i 从 1 到 len(S1)，内层循环 j 从 1 到 len(S2)。

3. 0-1 背包问题

特点： 每件物品只有一件，你只能选择放或不放（0 或 1）。

场景： 你要打包旅行，每件衣服只有一件，你决定带哪几件。

动态规划解法：

• DP 状态： dp[i][j] 表示在前 i 件物品中选择，背包容量为 j 时，能获得的最大价值。

• 状态转移方程： 考虑第 i 件物品（假设其重量为 w[i-1]，价值为 v[i-1]）：

  1. 不选择第 i 件物品： 此时最大价值等于在前 i-1 件物品中选择，背包容量为 j 时的最大价值，即 dp[i-1][j]。
  2. 选择第 i 件物品： 前提是背包容量 j 足够放下第 i 件物品（即 j >= w[i-1]）。此时，剩余容量为 j - w[i-1]，我们需要在前 i-1 件物品中选择，获得 dp[i-1][j - w[i-1]] 的价值，再加上第 i 件物品的价值 v[i-1]。所以是 dp[i-1][j - w[i-1]] + v[i-1]。

  综上，当 j < w[i-1] 时，dp[i][j] = dp[i-1][j]。 当 j >= w[i-1] 时，dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])。

• 初始状态： dp[0][j] = 0 (没有物品时，价值为0)，dp[i][0] = 0 (背包容量为0时，价值为0)。

• 遍历顺序： 外层循环物品 i (从 1 到 N)，内层循环背包容量 j (从 1 到 W)。

空间优化（一维数组）：

由于 dp[i][j] 只依赖于 dp[i-1][...]，我们可以将二维 dp 数组优化为一维 dp 数组。 dp[j] 此时表示背包容量为 j 时的最大价值。

• 状态转移： dp[j] = max(dp[j], dp[j - w[i]] + v[i])
• 遍历顺序： 关键在于内层循环 j 必须从 W 到 w[i] 逆序遍历。 这是为了确保在计算 dp[j] 时，dp[j - w[i]] 还是上一层（即不包含当前物品 i）的值。如果正序遍历，dp[j - w[i]] 可能已经被当前物品 i 更新过，导致物品 i 被重复选择。

Python

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n): # 遍历物品
        for j in range(capacity, weights[i] - 1, -1): # 逆序遍历容量
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
            
    return dp[capacity]

# 示例
# weights = [2, 1, 3]
# values = [4, 2, 3]
# capacity = 4
# print(knapsack_01(weights, values, capacity)) # Output: 6 (选择物品0和物品1)

4. 完全背包问题

特点： 每件物品有无限多件，你可以选择任意件数放入背包。

场景： 你去超市购物，每种商品想买多少就买多少（只要钱够，购物车放得下）。

动态规划解法：

与 0-1 背包的关键区别在于，选择当前物品后，它仍然可以再次被选择。

• DP 状态： dp[j] 表示背包容量为 j 时，能获得的最大价值。
• 状态转移方程： dp[j] = max(dp[j], dp[j - w[i]] + v[i])
• 遍历顺序： 与 0-1 背包不同的是，内层循环 j 必须从 w[i] 到 W 正序遍历。 这是因为在计算 dp[j] 时，如果 j - w[i] 已经包含了当前物品 i 的选择，那么我们就可以继续选择物品 i。正序遍历确保了 dp[j - w[i]] 已经“考虑”过当前物品 i 的选择。

Python

def complete_knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n): # 遍历物品
        for j in range(weights[i], capacity + 1): # 正序遍历容量
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
            
    return dp[capacity]

# 示例
# weights = [2, 1, 3]
# values = [4, 2, 3]
# capacity = 4
# print(complete_knapsack(weights, values, capacity)) # Output: 8 (选择2次物品0，或4次物品1，或2次物品1+1次物品0)

5. 多重背包问题

特点： 每件物品有固定的数量限制（例如，第 i 种物品有 count[i] 件）。

场景： 你去批货，每种商品商家限量供应。

动态规划解法：

多重背包可以看作是 0-1 背包和完全背包的结合。最直接的思路是将其转化为 0-1 背包问题。

转化思路：

将每件物品 i 及其数量 count[i] 展开成 count[i] 个独立的 0-1 背包问题中的物品。 例如，物品 A 有 3 件，重量 w_A，价值 v_A。我们可以把它看作 3 个独立的物品：A1 (w_A, v_A), A2 (w_A, v_A), A3 (w_A, v_A)。然后应用 0-1 背包的解法。

优化：二进制拆分

如果物品数量非常大，上述直接展开的方法会导致物品总数剧增，降低效率。更高效的方法是二进制拆分。 将每件物品 i 的数量 count[i] 拆分成若干个幂次为 2 的物品组合。 例如，如果 count[i] = 13，我们可以拆分成：

• 1 件物品 (价值 1 * v[i], 重量 1 * w[i])
• 2 件物品 (价值 2 * v[i], 重量 2 * w[i])
• 4 件物品 (价值 4 * v[i], 重量 4 * w[i])
• 8 件物品 (价值 8 * v[i], 重量 8 * w[i]) – 1 + 2 + 4 + 8 = 15 > 13，所以最后一个是 13 - (1+2+4) = 6 件物品 (价值 6 * v[i], 重量 6 * w[i])。

通过这种方式，任何 count[i] 件物品的选择都可以由这些二进制组合的物品来表示，而物品的总数大大减少。然后，对这些“新”物品应用 0-1 背包的解法。

Python

def multiple_knapsack(weights, values, counts, capacity):
    # 将多重背包问题转化为0-1背包问题
    # 使用二进制拆分优化
    
    binary_weights = []
    binary_values = []

    for i in range(len(weights)):
        w, v, c = weights[i], values[i], counts[i]
        k = 1
        while c > 0:
            num = min(k, c)
            binary_weights.append(w * num)
            binary_values.append(v * num)
            c -= num
            k *= 2 # 2的幂次
    
    # 转换为0-1背包问题求解
    n_binary = len(binary_weights)
    dp = [0] * (capacity + 1)

    for i in range(n_binary):
        for j in range(capacity, binary_weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - binary_weights[i]] + binary_values[i])
            
    return dp[capacity]

# 示例
# weights = [2, 3]
# values = [3, 4]
# counts = [2, 1] # 物品0有2件，物品1有1件
# capacity = 5
# print(multiple_knapsack(weights, values, counts, capacity)) # Output: 7 (选择2件物品0，或1件物品0+1件物品1)