记忆化 vs 递推 · dynamic programming step-by-step
很多人觉得动态规划很玄，其实它就是"递归 + 记忆化"。同一个子问题第二次被问到时，直接查表返回，不再往下递归。
暴力递归算 fib(5) 时，fib(2) 被算了 3 次，fib(3) 被算了 2 次。n 一大，重复呈树形爆炸——fib(40) 的递归树有约 1.65 亿个节点，其中 fib(2) 一个就被算了约 3900 万次。DP 把这棵树压成一条线，每个 fib(k) 只算一次。
选问题、设 n、点"下一步"，看每个子问题被"点亮"的顺序。自顶向下从 fib(n) 往下递归（带记忆化），自底向上从 fib(0) 往上推。
不是所有递归都该改成 DP。DP 有两个前提：
同一个子问题被多次计算。fib 满足，归并排序不满足（每个子数组只排一次）。
大问题的最优解由小问题的最优解组合而成。最短路满足，最长路径不一定。
状态 = (i, j)，转移 = 从几个子状态取最优。表格法直接套。
子问题不重叠用分治；局部最优即全局最优用贪心，不必存表。
判断顺序：先看能不能拆成子问题，再看子问题重不重叠，最后看是不是求最优/计数。三个都满足，DP 就是首选。