算法概念速查
什么是动态规划？状态、转移方程、边界三件事讲透入门
一句话定义
动态规划（DP）是解决「大问题由重叠子问题组成」的方法：用一张表把每个子问题的答案记下来，从最小的情况出发，按转移方程一步步推到目标——每个子问题只算一次，查表复用。写一个 DP 只需回答三件事：状态是什么（dp[i] 表示什么）、转移方程怎么写（dp[i] 由哪些更小的状态推出）、边界是什么（最小的几个状态直接给值）。
先打个比方
像爬楼梯时在每级台阶上贴张便利贴：想知道到第 10 级有几种走法，不用每次都从头数——第 9 级和第 8 级的便利贴上已经写好了答案，加起来就是第 10 级的。DP 的全部秘密就是「把算过的答案写在便利贴上，后面的人直接抄」。
它是怎么运作的
为什么暴力递归慢、DP 快？递归算 f(10) 会把 f(8) 算两遍、f(7) 算三遍……重复计算指数爆炸。DP（或记忆化）保证每个子问题只算一次，n 个状态、每个转移 O(1)，就是 O(n)。所以判断能不能 DP，先看两个性质：子问题重叠（同一个小问题被反复用到）、最优子结构（大问题的答案能由小问题的答案组合出来）。
入门期最该练的基本功是「用一句完整的话定义状态」：比如打家劫舍的 dp[i] = 「只考虑前 i 间房能偷到的最大金额」。这句话说不利索，转移方程一定写不出来；说清楚了，转移往往就是把「最后一步的所有可能」分类讨论一遍。
什么时候用：识别信号
题目里出现下面任何一条，就该想到「动态规划」。
- 求「最大 / 最小 / 多少种方案 / 能否达成」，而不要求列出每个方案
- 当前的选择会影响后面的选择（今天偷了这家，明天就不能偷邻居）
- 暴力递归画出的调用树里，同一个子问题出现了很多次
- 问题规模能用一两个参数刻画，且大规模答案由小规模答案组合而来
别和它们搞混
配套动画题：眼见为实
每道题都有逐步交互动画，看着数据动起来，比读十遍文字都快。
常见追问
状态定义有套路吗？
常用三板斧：「前 i 个元素的……」（线性 DP）、「以 i 结尾的……」（子数组/子序列类）、「区间 [i, j] 的……」（区间 DP）。定义完自问一句：目标答案能直接从表里读出来吗？读不出来就调整定义。
DP 数组一定是一维的吗？
维度跟着状态走：一个参数够描述子问题就一维（爬楼梯），需要「位置 + 是否持股」就二维（股票系列），背包要「前 i 件 + 容量 j」也是二维。先把状态说清楚，维度自然浮出来。
空间怎么优化？
看转移只依赖哪些旧状态：只用 dp[i-1]、dp[i-2] 就滚动两个变量（O(1)）；二维只依赖上一行就压成一维滚动数组。优化前先保证朴素版写对。