BLOG

主题

子序列与子串攻坚计划 ​

三道核心题的难度呈递进关系，建议严格按顺序分站突破。

第 1 站 · LeetCode 5 最长回文子串 ​

  • 选择理由：dp[i][j] 的定义最直观，是二维回文子串类题目的入门模板。

DP 五步法 ​

  1. 状态定义：dp[i][j] 表示 s[i…j] 是否为回文串，取值为布尔值。
  2. 状态转移：
    • 当 s[i] 与 s[j] 不相等时，dp[i][j] 恒为 false。
    • 当 s[i] 与 s[j] 相等时，取决于内部子串是否为回文：dp[i+1][j-1]。
    • 公式：dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]。
  3. 初始条件：
    • 子串长度为 1，dp[i][i] = true。
    • 子串长度为 2，dp[i][i+1] = (s[i] === s[i+1])。
  4. 遍历顺序：因为依赖左下角元素，必须按子串长度 L 递增遍历，或 i 递减、j 递增的斜向方式填表。
  5. 答案更新：每次 dp[i][j] 为 true 时，用 j - i + 1 与当前最大长度比较并记录区间。

第 2 站 · LeetCode 300 最长递增子序列 ​

  • 选择理由：引入「以 i 结尾」的状态定义思维，是一维序列 DP 的核心套路。

DP 五步法 ​

  1. 状态定义：dp[i] 表示必须以 nums[i] 结尾的最长递增子序列长度。
  2. 状态转移：遍历 j ∈ [0, i)，若 nums[i] > nums[j]，则可接在 dp[j] 后得到 dp[j] + 1，dp[i] 取这些候选的最大值。
  3. 初始条件：所有元素至少成长度为 1 的序列，因此 dp[i] 初始为 1。
  4. 遍历顺序：i 从 0 递增至 n - 1，内层回看所有 j < i。
  5. 结果获取：答案是 max(dp[0], …, dp[n-1])，而非 dp[n-1]。

第 3 站 · LeetCode 1143 最长公共子序列 ​

  • 选择理由：经典二维匹配模型，检验「双前缀」「是否相等」的 DP 思维。

DP 五步法 ​

  1. 状态定义：dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。
  2. 状态转移：
    • 若 text1[i-1] === text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
    • 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
  3. 初始条件：dp[0][j] 与 dp[i][0] 都为 0，对应任意串与空串的 LCS 长度。
  4. 遍历顺序：i 从 1 递增至 n，j 从 1 递增至 m。
  5. 最终答案：dp[n][m]。

暂缓背包的理由 ​

虽然 416 分割等和子集与 322 零钱兑换都属于背包范畴，但在熟悉子串与子序列 DP 之前无需分散精力。先把三个子串题啃透，再回看背包模型，理解会更顺畅。

阶段化训练路线 ​

阶段一 · 一维 DP（Sequence DP） ​

  • 目标：熟悉 dp[i] 的定义与线性转移。
  • 题单：
    1. LeetCode 70 爬楼梯：dp[i] = dp[i-1] + dp[i-2]。
    2. LeetCode 746 使用最小花费爬楼梯：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
    3. LeetCode 198 打家劫舍：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

阶段二 · 二维 DP（Grid/Matrix DP） ​

  • 目标：掌握 dp[i][j] 与双维度依赖。
  • 题单：
    1. LeetCode 62 不同路径：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
    2. LeetCode 64 最小路径和：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

阶段三 · 背包模型（Knapsack DP） ​

  • 目标：理解容量限制下的选取策略。
  • 题单：
    1. LeetCode 416 分割等和子集：dp[i][j] 表示前 i 个数能否填满容量 j。
    2. LeetCode 322 零钱兑换：完全背包求最值，dp[i] = min(dp[i - coin] + 1)。
    3. LeetCode 518 零钱兑换 II：完全背包求组合数。
    4. LeetCode 139 单词拆分：将字符串视为背包容量，字典单词视为物品。

阶段四 · 子序列与子串 DP（LCS 与 LIS） ​

  • 目标：区分连续与非连续的定义方式。
  • 题单：
    1. LeetCode 300 最长递增子序列。
    2. LeetCode 1143 最长公共子序列。
    3. LeetCode 5 最长回文子串。

执行建议 ​

  • 严格按顺序练习，避免贪多导致模式混乱。
  • 每刷一道题先在纸上写出 DP 五步法的前四步，再开始编码。
  • 做完后进行间隔重复：三天、一周各复盘一次，验证记忆深度。
  • 阶段总结：当一类题刷完后，抽象出共性模板，例如打家劫舍系列的 max(dp[i-1], dp[i-2] + value)。

拓展练习：回文场景 ​

  1. LeetCode 647 回文子串

    • 任务：统计字符串中所有回文子串数量。
    • 思路：沿用中心扩散法，扩散成功一步就累计一次。

  2. LeetCode 516 最长回文子序列

    • 任务：求最长回文子序列长度。
    • 思路：中心扩散不再适用，需要 dp[i][j] 表示区间 [i, j] 内的最长回文子序列长度，按区间长度递增转移。

  3. LeetCode 131 分割回文串

    • 任务：将字符串切分为若干回文子串并返回所有方案。
    • 思路：回溯切割，每次在切割前用 DP 预处理或中心扩散判断 s[start…i] 是否为回文。

你已经掌握了中心扩散法，可优先尝试 LeetCode 647，检验自己能否独立完成全流程 AC。

本站访客数 人次 本站总访问量 次