30 秒识别Q1 · 746 Min Cost Climbing Stairs：每级台阶有一个花费，每次可以走 1 或 2 级，求走到楼顶的最小花费。你的第一反应是哪个模式？
看答案
一维 DP（模板 A）。dp[i] = cost[i] + min(dp[i-1], dp[i-2])，和爬楼梯是同一个骨架，只是把「方法数求和」换成「花费取 min」。
dp[i] 到底是「前 i 个的答案」还是「以 i 结尾的答案」——这是一维 DP 的分水岭，也是最常见的错误源头。两种定义各有主场：求「整体最优」（打家劫舍、爬楼梯、零钱兑换）用前 i 个，答案就是 dp[n]；求「必须包含某个元素」（最大子数组和、最长上升子序列）用以 i 结尾，答案是 max(dp) 而不是 dp[n]。取错定义，转移方程会怎么写都不顺。
写完转移别急着优化。dp[i] 只依赖前一两项时才做滚动变量（模板 A 的 prev/cur），先把完整的 dp 数组写对再压缩——面试里也建议这个顺序，省下的空间讲一句就行。
| 题面出现… | 想到 |
|---|---|
| 「有多少种方法 / 最少多少步」且答案只由前几项决定 | 线性 DP（模板 A） |
| 「不能取相邻的两个」 | 打家劫舍骨架：选它就得跳过前一个 |
| 「凑出金额 / 能否拆分成若干段」 | 完全背包式（模板 B） |
| 「以 i 结尾的最长 / 最大」 | 状态定义必须带「以 i 结尾」，答案取 max(dp) |
| 数据规模 10⁴~10⁵ 且要最优值 | DP（回溯会超时，贪心不一定对） |
| 环形（首尾相接） | 拆成两条线性各跑一次（213） |
要方案本身是回溯（第 09 章），要方案数才是 DP——第 09 章的 377 就是这个分流。每一步的最优选择显而易见、且不需要回头改，那是贪心（第 15 章）；反例见模板 B 的第一条断言。状态需要两个下标（两个序列、容量 × 物品）→ 第 17 章；「最长上升子序列」这一族虽然也是一维数组，但状态定义和转移自成一套 → 第 18 章。
■ 【骨架】 不变，闭着眼默写 ■ 【插槽】 随题变化，写题前先问自己填什么
def rob(nums):
prev = cur = 0 # 【骨架】cur = 前 i 间房的最优,prev = 前 i-1 间
for x in nums: # 【骨架】
prev, cur = cur, max(cur, prev + x) # 【插槽】转移:不选这间 / 选这间(+ 前前的最优)
return cur # 【插槽】答案:最后一项 / 全程最大 / 计数dp 数组，确认对了再压成 prev/cur。def coin_change(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount # 【骨架】dp[t] = 凑出 t 的最优值;INF = 凑不出
for t in range(1, amount + 1): # 【骨架】按容量从小到大填
for c in coins: # 【插槽】枚举"最后一步用了哪个"
if c <= t: # 【骨架】
dp[t] = min(dp[t], dp[t - c] + 1) # 【插槽】min 求最少 / += 求方案数
return -1 if dp[amount] == INF else dp[amount] # 【插槽】不可达怎么表示dp[i] = 走到第 i 级的方法数」这句话——状态定义的习惯从这里开始养。dp[i-1]，偷这间 = dp[i-2] + nums[i]」。INF 表示不可达，最后判一次；别用 -1 当哨兵，min 会把它选走。dp[t] 从最优值换成布尔可达性。字典先转 set；被追问优化时提「按单词长度枚举而不是遍历整个字典」。'0' 的边界：'0' 不能单独解码，'06' 也不是合法的两位数。写之前先把这两条列出来。dp 数组不够用时，就开两个。dp[i] 表示到 i 为止的结果」这种说法没有信息量。必须明确到「前 i 个」还是「以 i 结尾」，以及答案是 dp[n] 还是 max(dp)。max(dp)。写成 dp[-1] 时，最大子数组和、最长上升子序列都会在「最优段不在末尾」的用例上出错。min(dp[t], dp[t-c] + 1) 会把 -1+1=0 选进来。用 float('inf') 或 amount + 1。dp 数组，再压成滚动变量。213 这类需要「两次线性」的题，压缩后更难调试。30 秒识别Q1 · 746 Min Cost Climbing Stairs：每级台阶有一个花费，每次可以走 1 或 2 级，求走到楼顶的最小花费。你的第一反应是哪个模式？
一维 DP（模板 A）。dp[i] = cost[i] + min(dp[i-1], dp[i-2])，和爬楼梯是同一个骨架，只是把「方法数求和」换成「花费取 min」。
30 秒识别Q2 · 518 Coin Change II：给定面额，求凑出目标金额的组合数（1+2 和 2+1 算同一种）。你的第一反应是哪个模式？
一维 DP（模板 B 的计数版）。关键在循环顺序：外层物品、内层容量才是组合数；反过来会把 1+2 和 2+1 数成两种（那是 377 排列数）。同一个骨架，两层循环换个位置就是两道不同的题。
30 秒识别Q3 · 55 Jump Game：数组里每个数表示在该位置最多能向前跳几步，判断能否从起点跳到终点。你的第一反应是哪个模式？
贪心，不是本章——dp[i] = 能否到达 i 的写法是 O(n²) 且会超时；只维护「目前能到的最远位置」就够，O(n)。能一句话说清每步该选谁、且不需要回头改，优先贪心。见第 15 章。
每章自测都会混入恰好一道非本章题，防止「读哪章选哪章」的条件反射；题面也一律取自本章未收录的题，避免凭记忆而非凭信号作答。