一句话：把大问题拆成一堆小问题，答案存进表里；大问题需要时直接查表，而不是重新算一遍。
同一个子问题在递归里被反复求解。这是 DP 存在的前提——既然要重复算，那就只算一次、存下来。
大问题的最优答案，一定是由某个子问题的最优答案「拼」出来的。子问题选错了，这条路就走不通。
用一句人话说清 dp[i] 到底代表什么。定义错了，后面全错；定义对了，方程自己会浮出来。
从「已经知道的格子」推出「当前格子」。本质上是在枚举：最后一步有哪几种走法，分别对应哪个旧状态。
用最朴素的递归算 f(4) = f(3) + f(2)。整棵树里只有 5 个不同的子问题，却发生了 9 次函数调用。点击「下一步」，看看重复是从哪里冒出来的。
134 万 次函数调用，但其中只有 31 个不同的子问题。每多算一层，重复量翻倍——这就是为什么朴素递归会「慢到跑不完」。把算过的结果存进数组，复杂度立刻从 O(2ⁿ) 掉到 O(n)。一次可以走 1 级或 2 级，问走到第 9 级共有多少种走法。先别想公式——从「最后一步是怎么迈上来的」想，递推关系自己就出来了。
dp[0] = 1（站在地面算 1 种走法，不是 0）、dp[1] = 1。写转移方程前先把这两个值想清楚，否则后面全是 0。顺带一提：每格只依赖左边两格，所以可以只用两个变量滚动，空间从 O(n) 压到 O(1)。4 件物品，背包容量 5。每件只能拿或不拿。当「容量」和「物品数」同时变化时，一维的 dp[i] 就不够用了——必须开成二维：前 i 件物品、容量恰好为 j 时的最大价值。
"ABCB" 和 "BDCB" 两条轴摆成网格，格子里是「两个前缀的答案」。填完之后别急着走——从右下角顺着箭头回溯，答案是一路捡回来的。
max(上方, 左方)。这个「同则斜、异则取大」的结构，编辑距离、最长回文子序列几乎照抄。上面四道题看起来差很远，但动手时的思路是同一套。按顺序问自己下面五个问题，基本不会卡住。
把 dp[i] / dp[i][j] 念成一句完整的中文：「前 i 件物品、容量为 j 时能装的最大价值」。如果这句话说不通顺，说明状态维度还没想明白。
问自己：到达这个状态的最后一步，有哪几种可能？爬楼梯是「最后迈 1 级还是 2 级」，背包是「这件拿还是不拿」，LCS 是「这两个字符相不相等」。每一种可能对应一个旧状态，全部列出来取 max / min / 求和。
dp[0]、dp[0][j]、dp[i][0] 这些格子递推式覆盖不到，必须手写。它们错了，整张表都会跟着错，而且错得很隐蔽。
算 dp[i][j] 时要用到 dp[i-1][j] 和 dp[i-1][j-w]——上一行、左边。所以要外层按物品、内层按容量，从小到大。顺序错了会读到还没算的值（通常是 0），答案就莫名其妙偏小。
爬楼梯的答案是 dp[n]，LCS 是 dp[n][m]，但背包是 dp[n][W]（容量维度也要看满），区间 DP 往往需要遍历所有 dp[i][j] 取最优。填完表先回头确认一遍：题目要的是哪一格。
| 模型 | 状态定义 | 典型题型 |
|---|---|---|
| 线性 DP | dp[i] 前 i 个元素的答案 | 爬楼梯、打家劫舍、最大子段和、最长递增子序列 |
| 背包 DP | dp[i][j] 前 i 件、容量 j | 0-1 背包、完全背包、子集和、零钱兑换 |
| 双序列 DP | dp[i][j] S1 前 i 个 vs S2 前 j 个 | 最长公共子序列、编辑距离、最长公共子串 |
| 区间 DP | dp[l][r] 区间 [l, r] 的答案 | 最长回文子序列、石子合并、括号匹配 |
| 树形 DP | dp[u][0/1] 以 u 为根的子树、u 选或不选 | 打家劫舍 III、树的直径、没有上司的舞会 |