LLM 101

主题

二维 DP · DP 2D ​

一句话骨架：状态由两个维度共同决定——网格题里是 (行, 列)；双串题里是 (s1 的前缀长度, s2 的前缀长度)；区间题里是 (左端点, 右端点)。

解题四步 ​

  1. 状态定义：dp[i][j] 表示什么子结构？（网格→到达；双串→前缀对的最优；区间→[i..j] 的某种性质）
  2. 转移方程：枚举上一步从哪里来——网格三方向 / 双串四种末位组合 / 区间按长度切分。
  3. 初始化：第一行第一列对应"边界场景"（空串、单格）。
  4. 空间优化：双串和网格通常只依赖上一行+当前行，可压成一维。

通用模板 ​

python
# 双串前缀 DP 通用骨架
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]  # 哨兵行/列
# 边界
for i in range(m + 1):
    dp[i][0] = base_i
for j in range(n + 1):
    dp[0][j] = base_j
# 转移
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s1[i - 1] == s2[j - 1]:
            dp[i][j] = transition_match(dp[i-1][j-1])
        else:
            dp[i][j] = transition_mismatch(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
return dp[m][n]

关卡 1 · 不同路径 ​

学习目标

掌握网格类二维 DP 的"上方+左方"加法递推，理解一维滚动数组中 dp[j] += dp[j-1] 为什么从左往右更新就刚好对应"上方旧值+左方新值"。

#62不同路径中等
♥♥♥♥♥+0 XP🔥 0
0 / 12

📝 题目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 「Start」）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（标记为 「Finish」）。

问总共有多少条不同的路径？
示例 1
输入m = 3, n = 7
输出28
示例 2
输入m = 3, n = 2
输出3
示例 3
输入m = 7, n = 3
输出28
💡 行列对换答案不变（组合数对称）
约束
  • 1 ≤ m, n ≤ 100
  • 题目保证答案小于等于 2 × 10⁹
💡 思路：到达 (i, j) 只能来自正上方 (i-1, j) 或正左方 (i, j-1)，所以 dp[i][j] = dp[i-1][j] + dp[i][j-1]。第一行只能从左来 → 全 1；第一列只能从上来 → 全 1。由于 dp[i][j] 只依赖"上方"和"左方"，可以用一维滚动数组：从左往右遍历时，`dp[j]`（更新前）= 上方旧值，`dp[j-1]`（已更新）= 左方新值。

✅ 完整解法

时间 O(m·n) · 空间 O(n)（一维滚动）或 O(1) 用组合数公式

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def uniquePaths(m: int, n: int) -> int: 2    # 一维滚动:dp[j] 表示「到达当前行第 j 列」的路径数 3    dp = [1] * n  # 第一行全部为 1 4    for i in range(1, m): 5        # dp[0] 始终是 1(第一列只能从上面下来) 6        for j in range(1, n): 7            dp[j] = dp[j] + dp[j - 1]  # 上方 + 左方 8    return dp[n - 1]

🐞 单步可视化

示例：m = 3, n = 3
代码L3
 1def uniquePaths(m: int, n: int) -> int: 2    # 一维滚动:dp[j] 表示「到达当前行第 j 列」的路径数 3    dp = [1] * n  # 第一行全部为 1 4    for i in range(1, m): 5        # dp[0] 始终是 1(第一列只能从上面下来) 6        for j in range(1, n): 7            dp[j] = dp[j] + dp[j - 1]  # 上方 + 左方 8    return dp[n - 1]
数据流
m3n3
j=0
j=1
j=2
i=0
1
1
1
i=1
1
·
·
i=2
1
·
·
1 / 11初始化第一行全为 1（边界）

🧠 理解检验

每题都对应解法的某一行或某个决策
dp[i][j] 的状态定义是？
转移方程是？
边界——第一行 dp[0][j] 与第一列 dp[i][0] 应当填什么？
一维滚动数组中 dp[j] = dp[j] + dp[j-1] 的含义是？
 1def uniquePaths(m: int, n: int) -> int: 2    # 一维滚动:dp[j] 表示「到达当前行第 j 列」的路径数 3    dp = [1] * n  # 第一行全部为 1 4    for i in range(1, m): 5        # dp[0] 始终是 1(第一列只能从上面下来) 6        for j in range(1, n): 7            dp[j] = dp[j] + dp[j - 1]  # 上方 + 左方 8    return dp[n - 1]
一维滚动若改为从右往左遍历 j，会出什么问题？
为什么内层从 j=1 而不是 j=0 开始？
 1def uniquePaths(m: int, n: int) -> int: 2    # 一维滚动:dp[j] 表示「到达当前行第 j 列」的路径数 3    dp = [1] * n  # 第一行全部为 1 4    for i in range(1, m): 5        # dp[0] 始终是 1(第一列只能从上面下来) 6        for j in range(1, n): 7            dp[j] = dp[j] + dp[j - 1]  # 上方 + 左方 8    return dp[n - 1]
二维版 dp 数组初始化：dp = [[1]*n for _ in range(m)] 与 dp = [[1]*n]*m 的区别？
本题的纯组合数学解是？
时间复杂度是？
一维滚动后的空间复杂度是？
若网格存在障碍物（LC 63 不同路径 II），DP 应如何修改？
若返回值"很大"题目要求取模 10⁹+7，是否影响 DP 结构？

关卡 2 · 最长公共子序列 ​

学习目标

建立"双串前缀 DP"母题：末位相同 → dp[i-1][j-1]+1；末位不同 → max(dp[i-1][j], dp[i][j-1])。理解哨兵行/列与 1-indexed 对齐的细节。

#1143最长公共子序列中等
♥♥♥♥♥+0 XP🔥 0
0 / 12

📝 题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
示例 1
输入text1 = "abcde", text2 = "ace"
输出3
💡 LCS 为 "ace"
示例 2
输入text1 = "abc", text2 = "abc"
输出3
示例 3
输入text1 = "abc", text2 = "def"
输出0
约束
  • 1 ≤ text1.length, text2.length ≤ 1000
  • text1 与 text2 仅由小写英文字符组成
💡 思路：`dp[i][j]` = `text1[:i]` 与 `text2[:j]` 的 LCS 长度。考察第 i 个与第 j 个字符：① 相同 → 一定能进入 LCS，dp[i][j] = dp[i-1][j-1] + 1；② 不同 → 至少有一方放弃自己的末尾，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。第一行第一列全 0（任何串与空串的 LCS 是空）。

✅ 完整解法

时间 O(m·n) · 空间 O(m·n)（可压成 O(min(m,n))）

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def longestCommonSubsequence(text1: str, text2: str) -> int: 2    m, n = len(text1), len(text2) 3    # dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 长度 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    for i in range(1, m + 1): 6        for j in range(1, n + 1): 7            if text1[i - 1] == text2[j - 1]: 8                # 末位字符相同 → 必属于 LCS,前缀各退一格 9                dp[i][j] = dp[i - 1][j - 1] + 110            else:11                # 末位不同 → 至少一方不能用,取较优者12                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])13    return dp[m][n]

🐞 单步可视化

示例：text1 = "abcde", text2 = "ace"
代码L3
 1def longestCommonSubsequence(text1: str, text2: str) -> int: 2    m, n = len(text1), len(text2) 3    # dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 长度 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    for i in range(1, m + 1): 6        for j in range(1, n + 1): 7            if text1[i - 1] == text2[j - 1]: 8                # 末位字符相同 → 必属于 LCS,前缀各退一格 9                dp[i][j] = dp[i - 1][j - 1] + 110            else:11                # 末位不同 → 至少一方不能用,取较优者12                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])13    return dp[m][n]
数据流
m5n3
ε
0:a
1:c
2:e
ε
0
0
0
0
0:a
0
·
·
·
1:b
0
·
·
·
2:c
0
·
·
·
3:d
0
·
·
·
4:e
0
·
·
·
1 / 32初始化 dp 为 (m+1)×(n+1) 全 0；第 0 行/列对应空串，LCS 长度=0

🧠 理解检验

每题都对应解法的某一行或某个决策
dp[i][j] 的状态定义最准确的是？
当 text1[i-1] == text2[j-1] 时（注意索引偏移）转移为？
 1def longestCommonSubsequence(text1: str, text2: str) -> int: 2    m, n = len(text1), len(text2) 3    # dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 长度 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    for i in range(1, m + 1): 6        for j in range(1, n + 1): 7            if text1[i - 1] == text2[j - 1]: 8                # 末位字符相同 → 必属于 LCS,前缀各退一格 9                dp[i][j] = dp[i - 1][j - 1] + 110            else:11                # 末位不同 → 至少一方不能用,取较优者12                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])13    return dp[m][n]
当末尾不同时，转移 max(dp[i-1][j], dp[i][j-1]) 的含义？
 1def longestCommonSubsequence(text1: str, text2: str) -> int: 2    m, n = len(text1), len(text2) 3    # dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 长度 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    for i in range(1, m + 1): 6        for j in range(1, n + 1): 7            if text1[i - 1] == text2[j - 1]: 8                # 末位字符相同 → 必属于 LCS,前缀各退一格 9                dp[i][j] = dp[i - 1][j - 1] + 110            else:11                # 末位不同 → 至少一方不能用,取较优者12                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])13    return dp[m][n]
为什么不需要考虑 dp[i-1][j-1] 这一项作为 max 候选？
初始化 dp 大小为 (m+1) × (n+1)、第一行第一列全 0 的理由？
 1def longestCommonSubsequence(text1: str, text2: str) -> int: 2    m, n = len(text1), len(text2) 3    # dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 长度 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    for i in range(1, m + 1): 6        for j in range(1, n + 1): 7            if text1[i - 1] == text2[j - 1]: 8                # 末位字符相同 → 必属于 LCS,前缀各退一格 9                dp[i][j] = dp[i - 1][j - 1] + 110            else:11                # 末位不同 → 至少一方不能用,取较优者12                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])13    return dp[m][n]
注意索引：text1[i-1] 而不是 text1[i]，原因？
 1def longestCommonSubsequence(text1: str, text2: str) -> int: 2    m, n = len(text1), len(text2) 3    # dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 长度 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    for i in range(1, m + 1): 6        for j in range(1, n + 1): 7            if text1[i - 1] == text2[j - 1]: 8                # 末位字符相同 → 必属于 LCS,前缀各退一格 9                dp[i][j] = dp[i - 1][j - 1] + 110            else:11                # 末位不同 → 至少一方不能用,取较优者12                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])13    return dp[m][n]
若需要还原 LCS 字符串（不只是长度），思路是？
dp = [[0]*(n+1) for _ in range(m+1)] 与 dp = [[0]*(n+1)]*(m+1) 的差别？
时间复杂度是？
空间能压缩到？
LCS 与 "最长公共子串"（连续）的关键区别是？
LCS 与"最短公共超序列长度"（SCS, LC 1092）的关系？

关卡 3 · 编辑距离 ​

学习目标

学会"三方向对应三种操作"——dp[i-1][j-1] 替换、dp[i-1][j] 删除、dp[i][j-1] 插入；体会为什么第一行/列必须是"全插/全删"的递增序列。

#72编辑距离中等
♥♥♥♥♥+0 XP🔥 0
0 / 13

📝 题目

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1
输入word1 = "horse", word2 = "ros"
输出3
💡 horse → rorse(替换 h→r) → rose(删 r) → ros(删 e)
示例 2
输入word1 = "intention", word2 = "execution"
输出5
示例 3
输入word1 = "", word2 = "abc"
输出3
💡 插入 3 次
约束
  • 0 ≤ word1.length, word2.length ≤ 500
  • word1 与 word2 由小写英文字母组成
💡 思路：`dp[i][j]` = 把 `word1[:i]` 变成 `word2[:j]` 的最少操作。考虑末位 word1[i-1] vs word2[j-1]：① 相同 → 不用操作，dp[i][j] = dp[i-1][j-1]。② 不同 → 取三种操作中最少的：替换 dp[i-1][j-1]+1、删除 word1 末位 dp[i-1][j]+1、给 word1 末尾插入 word2[j-1] 即 dp[i][j-1]+1。第一行第一列分别对应"全插"和"全删"。

✅ 完整解法

时间 O(m·n) · 空间 O(m·n)（可压成 O(min(m,n))）

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def minDistance(word1: str, word2: str) -> int: 2    m, n = len(word1), len(word2) 3    # dp[i][j] = 把 word1[:i] 变成 word2[:j] 的最少操作数 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    # 第一列:word2 是空,word1[:i] 全删 → i 次 6    for i in range(m + 1): 7        dp[i][0] = i 8    # 第一行:word1 是空,要插入 j 次得到 word2[:j] 9    for j in range(n + 1):10        dp[0][j] = j11    for i in range(1, m + 1):12        for j in range(1, n + 1):13            if word1[i - 1] == word2[j - 1]:14                dp[i][j] = dp[i - 1][j - 1]  # 末位相同,不需要操作15            else:16                dp[i][j] = 1 + min(17                    dp[i - 1][j - 1],  # 替换 word1[i-1] 为 word2[j-1]18                    dp[i - 1][j],      # 删除 word1[i-1]19                    dp[i][j - 1],      # 在 word1 末尾插入 word2[j-1]20                )21    return dp[m][n]

🐞 单步可视化

示例：word1 = "horse", word2 = "ros"
代码L4
 1def minDistance(word1: str, word2: str) -> int: 2    m, n = len(word1), len(word2) 3    # dp[i][j] = 把 word1[:i] 变成 word2[:j] 的最少操作数 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    # 第一列:word2 是空,word1[:i] 全删 → i 次 6    for i in range(m + 1): 7        dp[i][0] = i 8    # 第一行:word1 是空,要插入 j 次得到 word2[:j] 9    for j in range(n + 1):10        dp[0][j] = j11    for i in range(1, m + 1):12        for j in range(1, n + 1):13            if word1[i - 1] == word2[j - 1]:14                dp[i][j] = dp[i - 1][j - 1]  # 末位相同,不需要操作15            else:16                dp[i][j] = 1 + min(17                    dp[i - 1][j - 1],  # 替换 word1[i-1] 为 word2[j-1]18                    dp[i - 1][j],      # 删除 word1[i-1]19                    dp[i][j - 1],      # 在 word1 末尾插入 word2[j-1]20                )21    return dp[m][n]
数据流
word1"horse"word2"ros"m5n3
ε
r
o
s
ε
·
·
·
·
h
·
·
·
·
o
·
·
·
·
r
·
·
·
·
s
·
·
·
·
e
·
·
·
·
1 / 46初始化 (6)×(4) DP 表

🧠 理解检验

每题都对应解法的某一行或某个决策
dp[i][j] 状态定义最准确的是？
当 word1[i-1] == word2[j-1] 时，转移是？
 1def minDistance(word1: str, word2: str) -> int: 2    m, n = len(word1), len(word2) 3    # dp[i][j] = 把 word1[:i] 变成 word2[:j] 的最少操作数 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    # 第一列:word2 是空,word1[:i] 全删 → i 次 6    for i in range(m + 1): 7        dp[i][0] = i 8    # 第一行:word1 是空,要插入 j 次得到 word2[:j] 9    for j in range(n + 1):10        dp[0][j] = j11    for i in range(1, m + 1):12        for j in range(1, n + 1):13            if word1[i - 1] == word2[j - 1]:14                dp[i][j] = dp[i - 1][j - 1]  # 末位相同,不需要操作15            else:16                dp[i][j] = 1 + min(17                    dp[i - 1][j - 1],  # 替换 word1[i-1] 为 word2[j-1]18                    dp[i - 1][j],      # 删除 word1[i-1]19                    dp[i][j - 1],      # 在 word1 末尾插入 word2[j-1]20                )21    return dp[m][n]
末位不同时三个候选 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 分别对应？
 1def minDistance(word1: str, word2: str) -> int: 2    m, n = len(word1), len(word2) 3    # dp[i][j] = 把 word1[:i] 变成 word2[:j] 的最少操作数 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    # 第一列:word2 是空,word1[:i] 全删 → i 次 6    for i in range(m + 1): 7        dp[i][0] = i 8    # 第一行:word1 是空,要插入 j 次得到 word2[:j] 9    for j in range(n + 1):10        dp[0][j] = j11    for i in range(1, m + 1):12        for j in range(1, n + 1):13            if word1[i - 1] == word2[j - 1]:14                dp[i][j] = dp[i - 1][j - 1]  # 末位相同,不需要操作15            else:16                dp[i][j] = 1 + min(17                    dp[i - 1][j - 1],  # 替换 word1[i-1] 为 word2[j-1]18                    dp[i - 1][j],      # 删除 word1[i-1]19                    dp[i][j - 1],      # 在 word1 末尾插入 word2[j-1]20                )21    return dp[m][n]
为什么"在 word1 末尾插入 word2[j-1]"对应 dp[i][j-1] 而不是 dp[i-1][j]？
边界 dp[i][0] = i 含义？
 1def minDistance(word1: str, word2: str) -> int: 2    m, n = len(word1), len(word2) 3    # dp[i][j] = 把 word1[:i] 变成 word2[:j] 的最少操作数 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    # 第一列:word2 是空,word1[:i] 全删 → i 次 6    for i in range(m + 1): 7        dp[i][0] = i 8    # 第一行:word1 是空,要插入 j 次得到 word2[:j] 9    for j in range(n + 1):10        dp[0][j] = j11    for i in range(1, m + 1):12        for j in range(1, n + 1):13            if word1[i - 1] == word2[j - 1]:14                dp[i][j] = dp[i - 1][j - 1]  # 末位相同,不需要操作15            else:16                dp[i][j] = 1 + min(17                    dp[i - 1][j - 1],  # 替换 word1[i-1] 为 word2[j-1]18                    dp[i - 1][j],      # 删除 word1[i-1]19                    dp[i][j - 1],      # 在 word1 末尾插入 word2[j-1]20                )21    return dp[m][n]
边界 dp[0][j] = j 含义？
 1def minDistance(word1: str, word2: str) -> int: 2    m, n = len(word1), len(word2) 3    # dp[i][j] = 把 word1[:i] 变成 word2[:j] 的最少操作数 4    dp = [[0] * (n + 1) for _ in range(m + 1)] 5    # 第一列:word2 是空,word1[:i] 全删 → i 次 6    for i in range(m + 1): 7        dp[i][0] = i 8    # 第一行:word1 是空,要插入 j 次得到 word2[:j] 9    for j in range(n + 1):10        dp[0][j] = j11    for i in range(1, m + 1):12        for j in range(1, n + 1):13            if word1[i - 1] == word2[j - 1]:14                dp[i][j] = dp[i - 1][j - 1]  # 末位相同,不需要操作15            else:16                dp[i][j] = 1 + min(17                    dp[i - 1][j - 1],  # 替换 word1[i-1] 为 word2[j-1]18                    dp[i - 1][j],      # 删除 word1[i-1]19                    dp[i][j - 1],      # 在 word1 末尾插入 word2[j-1]20                )21    return dp[m][n]
若 word1 == word2，DP 表的对角线 dp[i][i] 全部应该是？
为什么"末位相同"分支不需要把"删/插"也加入 min 比较？
编辑距离最少为 |m - n|，因为？
时间复杂度是？
空间能否压缩？
若题目改成"只允许插入和删除"（不允许替换），与 LCS 的关系是？
若三种操作的"代价不同"（如删除 cost=1、插入 cost=2、替换 cost=3），DP 框架要怎么改？

关卡 4 · 最长回文子串 ​

学习目标

对比"区间 DP（按长度填表）"与"中心扩展（O(1) 空间）"两种解法，理解为什么 DP 转移 dp[i][j]=dp[i+1][j-1] and s[i]==s[j] 必须先算更短的区间。

#5最长回文子串中等
♥♥♥♥♥+0 XP🔥 0
0 / 13

📝 题目

给你一个字符串 s，找到 s 中最长的回文子串。

（子串是连续的；与子序列不同。）
示例 1
输入s = "babad"
输出"bab"
💡 "aba" 也是合法答案
示例 2
输入s = "cbbd"
输出"bb"
💡 偶数中心
示例 3
输入s = "a"
输出"a"
约束
  • 1 ≤ s.length ≤ 1000
  • s 仅由数字和英文字母组成
💡 思路：两套主流思路：① **DP** —— `dp[i][j]` = `s[i..j]` 是否回文，转移 `dp[i][j] = dp[i+1][j-1] and s[i]==s[j]`；填表必须**按区间长度从小到大**才能保证 dp[i+1][j-1] 已就绪。② **中心扩展** —— 枚举每个可能的回文中心（n 个奇中心 + n-1 个偶中心），向两边扩展直到失败，记录最长。两者都是 O(n²) 时间，但中心扩展空间 O(1) 更优；最优算法是 Manacher 的 O(n)。

✅ 完整解法

时间 O(n²) · 空间 O(1)（中心扩展）

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def longestPalindrome(s: str) -> str: 2    n = len(s) 3    if n == 0: 4        return s  # 空串直接返回 5    start, max_len = 0, 1 6  7    def expand(left: int, right: int) -> None: 8        nonlocal start, max_len 9        # 两侧扩展直到不再回文或越界10        while left >= 0 and right < n and s[left] == s[right]:11            if right - left + 1 > max_len:12                start, max_len = left, right - left + 113            left -= 114            right += 115 16    for i in range(n):17        expand(i, i)      # 奇数中心(以 i 为中心)18        expand(i, i + 1)  # 偶数中心(以 i,i+1 为中心)19    return s[start:start + max_len]

🐞 单步可视化

示例：s = "babad"
代码L2
 1def longestPalindrome(s: str) -> str: 2    n = len(s) 3    if n == 0: 4        return s  # 空串直接返回 5    start, max_len = 0, 1 6  7    def expand(left: int, right: int) -> None: 8        nonlocal start, max_len 9        # 两侧扩展直到不再回文或越界10        while left >= 0 and right < n and s[left] == s[right]:11            if right - left + 1 > max_len:12                start, max_len = left, right - left + 113            left -= 114            right += 115 16    for i in range(n):17        expand(i, i)      # 奇数中心(以 i 为中心)18        expand(i, i + 1)  # 偶数中心(以 i,i+1 为中心)19    return s[start:start + max_len]
数据流
n5bests[0..0]="b"
j=0:b
j=1:a
j=2:b
j=3:a
j=4:d
i=0:b
·
·
·
·
·
i=1:a
·
·
·
·
i=2:b
·
·
·
i=3:a
·
·
i=4:d
·
1 / 27输入 s = "babad"，长度 n = 5；目标：dp[i][j] 表示 s[i..j] 是否回文

🧠 理解检验

每题都对应解法的某一行或某个决策
中心扩展法为什么要分"奇中心"和"偶中心"两种？
 1def longestPalindrome(s: str) -> str: 2    n = len(s) 3    if n == 0: 4        return s  # 空串直接返回 5    start, max_len = 0, 1 6  7    def expand(left: int, right: int) -> None: 8        nonlocal start, max_len 9        # 两侧扩展直到不再回文或越界10        while left >= 0 and right < n and s[left] == s[right]:11            if right - left + 1 > max_len:12                start, max_len = left, right - left + 113            left -= 114            right += 115 16    for i in range(n):17        expand(i, i)      # 奇数中心(以 i 为中心)18        expand(i, i + 1)  # 偶数中心(以 i,i+1 为中心)19    return s[start:start + max_len]
expand(i, i) 和 expand(i, i+1) 的初始状态分别表示？
 1def longestPalindrome(s: str) -> str: 2    n = len(s) 3    if n == 0: 4        return s  # 空串直接返回 5    start, max_len = 0, 1 6  7    def expand(left: int, right: int) -> None: 8        nonlocal start, max_len 9        # 两侧扩展直到不再回文或越界10        while left >= 0 and right < n and s[left] == s[right]:11            if right - left + 1 > max_len:12                start, max_len = left, right - left + 113            left -= 114            right += 115 16    for i in range(n):17        expand(i, i)      # 奇数中心(以 i 为中心)18        expand(i, i + 1)  # 偶数中心(以 i,i+1 为中心)19    return s[start:start + max_len]
while 条件 left >= 0 and right < n and s[left] == s[right] 的三个判断顺序敏感吗？
 1def longestPalindrome(s: str) -> str: 2    n = len(s) 3    if n == 0: 4        return s  # 空串直接返回 5    start, max_len = 0, 1 6  7    def expand(left: int, right: int) -> None: 8        nonlocal start, max_len 9        # 两侧扩展直到不再回文或越界10        while left >= 0 and right < n and s[left] == s[right]:11            if right - left + 1 > max_len:12                start, max_len = left, right - left + 113            left -= 114            right += 115 16    for i in range(n):17        expand(i, i)      # 奇数中心(以 i 为中心)18        expand(i, i + 1)  # 偶数中心(以 i,i+1 为中心)19    return s[start:start + max_len]
DP 解法 dp[i][j] 的状态定义是？
DP 转移 dp[i][j] = dp[i+1][j-1] and s[i]==s[j] 的依赖方向是？
DP 边界——长度 1 与长度 2 的初始化分别是？
DP 与中心扩展的复杂度对比？
nonlocal start, max_len 在内嵌函数中的作用？
 1def longestPalindrome(s: str) -> str: 2    n = len(s) 3    if n == 0: 4        return s  # 空串直接返回 5    start, max_len = 0, 1 6  7    def expand(left: int, right: int) -> None: 8        nonlocal start, max_len 9        # 两侧扩展直到不再回文或越界10        while left >= 0 and right < n and s[left] == s[right]:11            if right - left + 1 > max_len:12                start, max_len = left, right - left + 113            left -= 114            right += 115 16    for i in range(n):17        expand(i, i)      # 奇数中心(以 i 为中心)18        expand(i, i + 1)  # 偶数中心(以 i,i+1 为中心)19    return s[start:start + max_len]
为什么对每个 i 要调用 expand(i, i) 和 expand(i, i+1) 共两次？
时间复杂度是？
空间复杂度（中心扩展版）是？
若题目改成"统计回文子串的数量"（LC 647），思路差别？
若题目改成"最长回文子序列"（LC 516），上面代码还能用吗？

同 pattern 索引（hot100 同类题） ​

题号题名难度关键变形
64最小路径和中等把"求路径数"换成"求最小代价"：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
416分割等和子集中等0-1 背包：dp[i][j] = 前 i 个数能否凑出 j；可一维滚动倒序更新
120三角形最小路径和中等自底向上 DP，与 64 同模板但行长度递减
174地下城游戏困难反向 DP（从右下到左上）——典型"正向无后效性失败"案例
221最大正方形中等dp[i][j] = min(三邻居) + 1，状态是"以 (i,j) 为右下角的最大正方形边长"

面试常踩 ​

  1. 二维数组初始化的引用陷阱——[[0]*n]*m 让所有行共享引用，必须用列表推导式 [[0]*n for _ in range(m)]。
  2. 双串 DP 的索引对齐——dp 用 1-indexed（含哨兵），字符串用 0-indexed，转移里要写 s[i-1] 不是 s[i]。
  3. 区间 DP 的填表顺序——必须按区间长度从小到大，不能直接 i, j 双重循环顺序遍历，否则依赖未就绪。
  4. 滚动数组方向——一维压缩时方向决定正确性：本题（不同路径、LCS、编辑距离）从左往右；0-1 背包从右往左。