30 秒识别Q1 · 64 Minimum Path Sum：在一个数字网格里从左上走到右下，每次只能向右或向下，求路径数字和的最小值。你的第一反应是哪个模式？
看答案
二维 DP（模板 A）。dp[i][j] = grid[i][j] + min(上, 左)，和 62 是同一张表换了转移。看到「网格 + 只能右/下」就是二维 DP，不是图搜索——方向受限意味着没有环，不需要 visited。
双序列题（LCS、编辑距离、正则匹配）的表格永远长一个样：dp[i][j] 表示「a 的前 i 个和 b 的前 j 个」的答案。对上了走对角线，没对上各退一步——这两句话覆盖了本章一半的题。
背包的一维压缩是本章唯一需要死记的细节：01 背包倒序、完全背包正序。原因是倒序时 dp[t - x] 还停留在「上一件物品」的状态，正序时它已经被本轮更新过，等于允许同一件物品用多次。
| 题面出现… | 想到 |
|---|---|
| 「两个字符串 / 两个数组」比较、匹配、对齐 | dp[i][j] 双序列表（模板 A） |
| 「网格里从左上走到右下」（路径数 / 最小路径和） | dp[i][j] = 上 + 左 |
| 「能否把数组分成和相等的两半」 | 01 背包布尔版（模板 B） |
| 「加减号 / 分成两组」凑出目标 | 先转成子集和，再套背包（494） |
| 「编辑距离 / 最长公共子序列 / 通配符匹配」 | 模板 A，只换「对上/没对上」的转移 |
| 「带冷冻期 / 手续费的股票」 | 状态机 DP：dp[i][持有 or 空仓] |
状态只需要一个下标、且只依赖前一两项 → 第 16 章。「最长上升子序列」虽然也在比较元素大小，但只有一个序列、转移要回头看所有更早的元素，自成一套 → 第 18 章。要列出全部方案而不是计数 → 回溯（第 09 章）。「路径」这个词也要分三处：网格里只能右 / 下走 → 本章（方向受限、不可能有环，纯 DP）；能四向移动、求最少步数 → 第 10 章的 BFS；树上的路径和 → 第 07 章的递归。
■ 【骨架】 不变，闭着眼默写 ■ 【插槽】 随题变化，写题前先问自己填什么
def lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)] # 【骨架】多开一行一列当边界,省掉特判
for i in range(1, m + 1): # 【骨架】
for j in range(1, n + 1): # 【骨架】
if a[i - 1] == b[j - 1]: # 【插槽】两个维度"对上了"的条件
dp[i][j] = dp[i - 1][j - 1] + 1 # 【插槽】对上了怎么转移(走对角线)
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 【插槽】没对上:各退一步取最优
return dp[m][n] # 【插槽】答案在右下角i / j，LCS 填 0。def can_partition(nums):
total = sum(nums)
if total % 2: # 【插槽】问题先转化成"能否凑出某个目标"
return False
target = total // 2
dp = [False] * (target + 1) # 【骨架】dp[t] = 能否恰好凑出 t
dp[0] = True # 【骨架】什么都不选就能凑出 0
for x in nums: # 【骨架】外层枚举物品
for t in range(target, x - 1, -1): # 【骨架】容量倒序 —— 保证每个物品只用一次
dp[t] = dp[t] or dp[t - x] # 【插槽】布尔可行性 / 计数 / 最大价值
return dp[target]dp[i][j] = dp[i-1][j] + dp[i][j-1]。先用它把「多开一圈边界」的习惯建立起来，后面的题都省事。sum / 2。和为奇数直接返回 False，省一次 DP。P - (sum - P) = target，即 P = (sum + target) / 2。奇偶性不对或超界直接返回 0——这两个判断漏掉就会数组越界。hold（持有）/ sold（今天刚卖）/ rest（空仓且非冷冻）。画出三个状态之间的箭头再写代码，比硬推转移方程快得多。[1, 5, 11, 5] 会因为 5 被重复使用而误判。完全背包（零钱兑换）反过来正是要正序。if i == 0。(sum + target) 为奇数、或 |target| > sum 时无解。少了这两句会得到负的容量或错误答案。dp[i-1][j-1] 被覆盖，需要一个临时变量存左上角。面试里先写二维，被追问再说压缩方案。30 秒识别Q1 · 64 Minimum Path Sum：在一个数字网格里从左上走到右下，每次只能向右或向下，求路径数字和的最小值。你的第一反应是哪个模式？
二维 DP（模板 A）。dp[i][j] = grid[i][j] + min(上, 左)，和 62 是同一张表换了转移。看到「网格 + 只能右/下」就是二维 DP，不是图搜索——方向受限意味着没有环，不需要 visited。
30 秒识别Q2 · 1049 Last Stone Weight II：一堆石头两两相撞，剩下差值继续撞，求最后可能剩下的最小重量。你的第一反应是哪个模式？
01 背包（模板 B）。把石头分成两堆、让两堆重量尽量接近 —— 即在 sum/2 容量内能凑出的最大重量，答案是 sum - 2 * best。对比 1046（每次取最重的两块）才是堆：那道题按固定规则模拟，这道题要你自己分组。
30 秒识别Q3 · 139 Word Break：给一个字符串和一个词典，判断字符串能否拆成若干个词典里的单词。你的第一反应是哪个模式？
一维 DP，不是本章——虽然出现了「字符串 + 词典」两样东西，但状态只需要一个下标：dp[t] = 前 t 个字符能否拆完。词典是候选集合不是第二个序列，凑不出第二个维度。见第 16 章。
每章自测都会混入恰好一道非本章题，防止「读哪章选哪章」的条件反射；题面也一律取自本章未收录的题，避免凭记忆而非凭信号作答。