动态规划（DP）模块（6 题）

错题 1：斐波那契数列变形（爬楼梯问题）

• 错题题干：一个楼梯有 n 级，每次可以走 1 级或 2 级，求共有多少种不同的走法（n≤1000）。要求用 Python 实现，避免递归超时。
• 错误代码：

def climb_stairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    return climb_stairs(n-1) + climb_stairs(n-2)  # 递归未优化，n=30时已明显卡顿

• 错误原因分析：1. 未考虑递归的重复计算（如计算 climb_stairs (5) 时需重复计算 climb_stairs (3)、climb_stairs (2)）；2. 未使用动态规划的 “记忆化存储” 或 “递推” 思路，导致时间复杂度 O (2ⁿ)，n 稍大即超时。
• 正确代码：

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n+1)  # 递推式：dp[i] = dp[i-1] + dp[i-2]（第i级的走法=第i-1级走1步+第i-2级走2步）
    dp[1], dp[2] = 1, 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

• 复盘总结：处理 “重复子问题” 类 DP 题时，优先用 “递推”（迭代）替代递归，或给递归加 “记忆化装饰器（lru_cache）”，将时间复杂度降至 O (n)；需明确 DP 数组的定义（如本题 dp [i] 代表 “到第 i 级的总走法数”）。

错题 2：0-1 背包问题（基础版）

• 错题题干：有 n 个物品，每个物品重量 w [i]、价值 v [i]，背包最大承重为 C，求背包能装下的最大价值（每个物品仅选 1 次）。示例：n=3，w=[2,3,4]，v=[3,4,5]，C=5，预期输出 7（选重量 2+3 的物品，价值 3+4=7）。
• 错误代码：

def knapsack(w, v, C):
    n = len(w)
    dp = [[0]*(C+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, C+1):
            if w[i] > j:  # 错误：w是0索引，w[i]对应第i+1个物品，应改为w[i-1]
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
    return dp[n][C]

• 错误原因分析：1. 数组索引混淆：DP 表的 i 从 1 开始（代表 “前 i 个物品”），但物品重量 / 价值数组 w、v 是 0 索引，误将 w [i]、v [i] 当作第 i 个物品的属性，导致数组越界或取值错误；2. 未验证边界（如 i=1 时，w [1] 实际是第二个物品的重量，与 “前 1 个物品” 逻辑矛盾）。
• 正确代码：

def knapsack(w, v, C):
    n = len(w)
    dp = [[0]*(C+1) for _ in range(n+1)]
    for i in range(1, n+1):
        curr_w, curr_v = w[i-1], v[i-1]  # 明确当前处理的是第i个物品（w[i-1]、v[i-1]）
        for j in range(1, C+1):
            if curr_w > j:
                dp[i][j] = dp[i-1][j]  # 装不下当前物品，继承前i-1个物品的最大价值
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - curr_w] + curr_v)  # 选/不选当前物品的最大值
    return dp[n][C]

• 复盘总结：处理 DP 表与原数组的对应关系时，需提前定义 “索引含义”（如 i=1→前 1 个物品），并用变量（curr_w、curr_v）承接当前属性，避免索引混淆；写完后用小示例（如题干示例）验证，快速定位取值错误。

错题 3：最长递增子序列（LIS）

• 错题题干：给定整数数组 nums，求最长严格递增子序列的长度（子序列不要求连续）。示例：nums=[10,9,2,5,3,7,101,18]，预期输出 4（子序列 [2,3,7,101]）。
• 错误代码：

def length_of_lis(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # dp[i]代表以nums[i]结尾的LIS长度
    for i in range(n):
        for j in range(i+1, n):  # 错误：j应遍历i之前的元素（j < i），而非之后
            if nums[j] > nums[i]:
                dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

• 错误原因分析：1. 内层循环逻辑颠倒：要计算 “以 nums [i] 结尾的 LIS”，需对比 i 之前所有比 nums [i] 小的元素（j < i），而非 i 之后的元素；2. 原代码中 i 遍历所有元素，j 遍历 i 之后，导致 dp [i] 未被正确更新（如 i=3 时，j=4、5...，无法利用 i=2 的 dp 值）。
• 正确代码：

def length_of_lis(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # 核心定义：dp[i] = 以nums[i]为最后一个元素的最长递增子序列长度
    for i in range(1, n):  # i从1开始（i=0时dp[0]=1，无需更新）
        for j in range(i):  # 遍历i之前的所有元素j
            if nums[j] < nums[i]:  # 若nums[j]比nums[i]小，可构成以nums[i]结尾的更长子序列
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)  # 最终LIS长度是dp数组的最大值（可能以任意元素结尾）

• 复盘总结：LIS 类题的核心是 “dp [i] 与前序元素的关联”，需明确 “j < i” 的遍历逻辑；若后续需优化时间复杂度（从 O (n²) 到 O (nlogn)），可改用 “贪心 + 二分”，但基础 DP 解法需先保证逻辑正确。

错题 4：最长公共子序列（LCS）

• 错题题干：给定两个字符串 text1 和 text2，求它们的最长公共子序列长度（子序列可不连续）。示例：text1="abcde"，text2="ace"，预期输出 3。
• 错误代码：

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m):
        for j in range(n):
            if text1[i] == text2[j]:
                dp[i][j] = dp[i-1][j-1] + 1  # 错误：i、j从0开始，dp[i-1][j-1]会出现-1索引
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

• 错误原因分析：1. DP 表索引未 “多开 1 位”：原代码 dp 数组大小为 m×n，i、j 从 0 开始，当 i=0 或 j=0 时，dp [i-1][j-1] 会访问负索引（如 i=0、j=0 时，dp [-1][-1] 报错）；2. 未利用 “dp [0][] 和 dp [][0] 均为 0” 的边界条件（空字符串与任何字符串的 LCS 长度为 0）。
• 正确代码：

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    # dp[i][j]代表text1前i个字符（text1[0..i-1]）与text2前j个字符（text2[0..j-1]）的LCS长度
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:  # 字符匹配，LCS长度+1（继承前i-1、j-1的结果）
                dp[i][j] = dp[i-1][j-1] + 1
            else:  # 字符不匹配，取“text1前i-1个与text2前j个”或“text1前i个与text2前j-1个”的最大值
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]  # 最终结果是text1全量与text2全量的LCS长度

• 复盘总结：处理字符串 DP 题时，建议 DP 表 “多开 1 行 1 列”，将边界条件（空字符串）内置，避免负索引错误；需清晰定义 dp [i][j] 对应的字符串范围（如 “前 i 个字符”），再关联原字符串的索引（i-1、j-1）。

错题 5：最大子数组和（ Kadane 算法变体）

• 错题题干：给定整数数组 nums，求一个连续子数组的最大和（子数组必须连续）。示例：nums=[-2,1,-3,4,-1,2,1,-5,4]，预期输出 6（子数组 [4,-1,2,1]）。
• 错误代码：

def max_sub_array(nums):
    dp = [0] * len(nums)
    dp[0] = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(nums[i], dp[i] + nums[i])  # 错误：应继承dp[i-1]的结果，而非dp[i]（未初始化）
    return max(dp)

• 错误原因分析：1. DP 状态转移逻辑错误：dp [i] 的定义是 “以 nums [i] 结尾的连续子数组的最大和”，正确转移应为 “dp [i] = max (nums [i], dp [i-1] + nums [i])”（要么单独取 nums [i]，要么接在 i-1 的子数组后）；2. 原代码用 dp [i]（未赋值）加 nums [i]，导致计算结果混乱（如 i=1 时，dp [1] = max (1, 0+1)=1，看似正确，但 i=2 时 dp [2] = max (-3, 1+(-3))=-2，实际应为 max (-3, dp [1]+(-3))=-2，此处巧合正确，但逻辑本质错误）。
• 正确代码：

def max_sub_array(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    max_sum = dp[0]  # 用变量记录全局最大值，避免最后遍历dp数组
    for i in range(1, n):
        # 核心逻辑：以nums[i]结尾的子数组，要么“只包含自己”，要么“包含i-1结尾的子数组”
        dp[i] = max(nums[i], dp[i-1] + nums[i])
        max_sum = max(max_sum, dp[i])  # 实时更新全局最大值
    return max_sum

• 复盘总结：“连续子数组” 类 DP 题的核心是 “dp [i] 与 dp [i-1] 的连续性”，需严格遵循 “以 nums [i] 结尾” 的定义；可优化空间复杂度（将 dp 数组改为单个变量 prev，记录 dp [i-1] 的值，空间从 O (n) 降至 O (1)）。

错题 6：整数拆分（求最大乘积）

• 错题题干：给定一个正整数 n（n≥2），将其拆分为 k 个正整数的和（k≥2），求这些整数的最大乘积。示例：n=10，预期输出 36（10=3+3+4，乘积 3×3×4=36）。
• 错误代码：

def integer_break(n):
    dp = [0]*(n+1)
    dp[2] = 1  # 2=1+1，乘积1
    for i in range(3, n+1):
        for j in range(1, i):
            dp[i] = max(dp[i], j * (i-j))  # 错误：未考虑“i-j继续拆分”的情况（如i=4，j=2时，i-j=2，拆分后2=1+1，乘积2×1×1=2，比2×2=4小，但i=5时j=2，i-j=3，拆分后3=2+1，乘积2×2×1=4>2×3=6？不，2×3=6更大，此处需包含“j×dp[i-j]”的情况）
    return dp[n]

• 错误原因分析：1. 状态转移未覆盖 “拆分到底” 的场景：dp [i] 的定义是 “i 拆分后的最大乘积”，对于 j（1≤j<i），有两种选择：① i 拆分为 j 和 (i-j)，乘积 j×(i-j)；② i 拆分为 j 和 (i-j 的拆分结果)，乘积 j×dp [i-j]；原代码只考虑了①，未考虑②（如 i=6，j=3 时，i-j=3，dp [3]=2，乘积 3×2=6，比 3×3=9 小，但 j=2 时，i-j=4，dp [4]=4，乘积 2×4=8>2×4=8，正确情况需两者取 max）。
• 正确代码：

def integer_break(n):
    dp = [0]*(n+1)
    dp[2] = 1  # 边界：2只能拆1+1，乘积1
    for i in range(3, n+1):
        # j遍历1到i//2即可（因j和i-j对称，如j=1和j=i-1结果相同）
        for j in range(1, i//2 + 1):
            # 两种情况取max：j×(i-j)（不拆i-j）、j×dp[i-j]（拆i-j）
            current_max = max(j * (i-j), j * dp[i-j])
            dp[i] = max(dp[i], current_max)
    return dp[n]

• 复盘总结：处理 “拆分求最值” 类 DP 题时，需考虑 “拆分次数≥2” 的约束，状态转移需覆盖 “部分拆分” 和 “完全拆分” 两种情况；可通过 “遍历 j 到 i//2” 优化时间（减少重复计算）。