知识点深化 · 动态规划
动态规划：别重复算，把小问题答案记下来
求最大价值、最长子序列、最少步数……这些题暴力枚举会爆炸，动态规划（DP）的办法是：把大问题拆成小问题，算过的小问题存起来别重算。这一页从爬楼梯讲起，搞懂状态怎么定义、转移方程怎么写，亲手推一遍 01 背包和最长公共子序列。
① 小白第一课怎么学（4 步走，约 60 分钟）
动态规划就是"把大问题拆成小问题，并把小问题答案记下来别重算"：
1看直观（10 分钟）
读第②③部分：把 DP 想象成"爬楼梯，每步记住到每阶有几种走法"。
2记套路（15 分钟）
背第④部分：状态定义、转移方程、初始条件两大特征。
3做例题（20 分钟）
精读第⑤部分：背包、最长公共子序列手推一遍。
4刷题纠错（15 分钟）
做第⑦⑩部分，错题回到第⑥部分。
本课小目标学完你要能：① 判断一个题能不能用 DP；② 写出状态 dp[i] 和转移方程；③ 手推 01 背包和最长公共子序列的表格。
② 一图看懂：DP 在干嘛
读法：DP 两大前提（最优子结构、重叠子问题）→ 定义状态 dp[i] → 写转移方程 → 从底向上填表。
③ 先认识它：DP 就是"别重复算，记下来"
爬楼梯：一次能上 1 阶或 2 阶，问上到第 n 阶有几种走法？
· 想到第 n 阶，最后一步要么从 n−1 跨 1 阶，要么从 n−2 跨 2 阶。
· 所以 dp[n] = dp[n−1] + dp[n−2]。
· 这就是斐波那契数列！如果用纯递归，dp[5] 会反复算 dp[2] 很多遍；用 DP 就从 1 阶开始往上填表，每个只算一次。
DP = 递归 + 备忘录（把算过的小问题存起来）。
什么时候想到 DP题目问"最大/最小/方案数/是否可行"，且大问题能拆成同结构小问题、小问题还会重复出现——这就是 DP 的信号。
④ 完整体系与公式表
DP 两大特征
| 特征 | 含义 |
|---|
| 最优子结构 | 大问题的最优解，由小问题的最优解组合而来 |
| 重叠子问题 | 递归过程中同一小问题被反复求解，存起来复用 |
DP 解题四步
标准套路
① 定义状态 dp[i] 表示什么 ② 写转移方程 dp[i]=? ③ 定初始条件 dp[0]=? ④ 从底向上填表
01 背包问题
有 n 件物品，第 i 件重 w[i]、值 v[i]，背包容量 W，每件只能选一次，求最大价值。
状态 dp[i][j]：前 i 件、容量 j 时的最大价值
不选第 i 件：dp[i][j] = dp[i−1][j]
选第 i 件（j≥w[i]）：dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i])
最长公共子序列 LCS
求两个序列 A、B 的最长公共子序列长度。dp[i][j]=A 前 i 个、B 前 j 个的 LCS 长度。
转移方程
若 A[i]=B[j]：dp[i][j] = dp[i−1][j−1] + 1
否则：dp[i][j] = max(dp[i−1][j], dp[i][j−1])
DP 复杂度状态数 × 每状态转移代价。背包是 O(nW)，LCS 是 O(mn)。
⑤ 应用场景与典型例题
例1（爬楼梯）一次上 1 或 2 阶，上到第 4 阶有几种走法？
dp[1]=1，dp[2]=2。
dp[3]=dp[2]+dp[1]=3；dp[4]=dp[3]+dp[2]=3+2=5 种。
例2（01 背包）容量 W=5，物品(重2值6)、(重3值10)、(重4值12)，最大价值？
枚举选法。
· 选前两件：2+3=5≤5，价值 6+10=16。
· 选第三件：价值 12。
· 只选第一件+第三件超重。
最大价值 16（选前两件）。
例3（LCS）A="ABC"，B="AC"，最长公共子序列多长？
逐格填表。
公共子序列 "AC"，长度 2。（AB 里取 A，再取 C）。
怎么检验状态定义对不对能否用更小的 dp 值推出当前 dp 值？能，状态就定义对了；推不出，换状态。
⑥ 高频错误诊断（4 条）
错误 1：状态定义含糊dp[i] 到底是"前 i 个的最优"还是"以 i 结尾的最优"，完全是两种题。定义必须先写死。
错误 2：初始条件漏了dp[0] 是整个表的地基，错一个后面全错。先把边界填对再填表。
错误 3：把 DP 当纯递归不加备忘录斐波那契纯递归是 O(2ⁿ)，加备忘录才是 O(n)。
错误 4：01 背包混淆"选/不选"每件只能选一次，转移必须从 dp[i−1] 来，不能用本行刚更新过的值（那是完全背包）。
⑦ 考点与真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 识别 DP | 问哪题适合 DP | 最优+重叠子问题 |
| 状态转移 | 写 dp[i] 递推 | 拆最后一步 |
| 背包/LCS | 填表求值 | 套转移方程 |
真题1. 动态规划问题通常需要哪两个性质？
真题2. 爬楼梯（1或2阶）dp[n] 的转移方程是？
真题3. 01 背包中，第 i 件物品重量为 w[i]，容量 j≥w[i] 时选它的转移是？
真题4. 斐波那契递归加备忘录后，时间复杂度从 O(2ⁿ) 降到？
⑧ 必背公式卡
两特征：最优子结构 + 重叠子问题 DP 入场券
四步：定状态→写转移→定初值→从底填表 标准套路
爬楼梯：dp[n]=dp[n−1]+dp[n−2] 斐波那契
01背包：max(dp[i−1][j], dp[i−1][j−w]+v) 选/不选
LCS：相等 dp[i−1][j−1]+1，否则 max(上,左) 两串对齐
备忘录：算过就存，别重复递归 O(2ⁿ)→O(n)
复杂度：状态数 × 转移代价 背包 O(nW)
⑨ 应用输出：用 DP 思维建模
建模场景：旅行预算分配
预算 1000 元，三个景点：门票(300)、住宿(500)、吃饭(400)，问预算内最大总价值。
· 这就是 01 背包：每件选/不选，dp[景点][预算]=最大价值。
· dp[1][300]=门票价值；dp[2][800]=门票+住宿。
· 填表到 dp[3][1000]，得到预算内最优组合。
· 本质：把"整个预算怎么花"拆成"第 i 个项目要不要花"。
口述训练说三句："DP 就是递归加备忘录；先定义 dp[i] 是什么，再写最后一步怎么拆；背包选不选、LCS 相等加 1。"
⑩ 分层练习 18 题（基础 6 + 中档 6 + 拔高 6）
▍基础 6 题
基础1DP 的两个必要性质？
最优子结构、重叠子问题。
基础2dp[1]=1，dp[2]=2，dp[3]=？
dp[3]=dp[2]+dp[1]=3。
基础3DP 为什么比纯递归快？
用备忘录存已算子问题，避免重复计算。
基础5LCS 里 A[i]=B[j] 时转移？
dp[i][j]=dp[i−1][j−1]+1。
基础6DP 填表一般从哪往哪？
从最小的初始状态从底向上填到目标。
▍中档 6 题
中档7爬楼梯 dp[5]=？（dp1=1,dp2=2）
dp3=3,dp4=5,dp5=8。
中档801 背包容量 W=5，物品(重2值3)(重3值4)，最大价值？
两件都选重5，价值 7。
中档9LCS A="AB",B="BA" 长度？
公共子序列 "A" 或 "B"，长度 1。
中档10什么叫最优子结构？
大问题最优解可由子问题最优解推出。
中档11完全背包和 01 背包区别？
完全背包每件可选无限次，转移用本行 dp[i][j−w]。
中档12最长上升子序列 LIS 状态怎么定义？
dp[i]=以第 i 个元素结尾的 LIS 长度。
▍拔高 6 题
拔高1301 背包空间优化为什么用一维数组倒序？
倒序更新保证用到的是上一层 dp[j−w]，避免同件物品被重复选。
拔高14LCS 复杂度？
两个串长 m、n，O(mn)。
拔高15DP 和分治的区别？
分治子问题互不重叠；DP 子问题重叠、靠备忘录复用。
拔高16矩阵连乘最少乘法次数用什么？
区间 DP，dp[i][j]=合并 i~j 的最小代价。
拔高17DP 和贪心的区别？
贪心每步选局部最优不回看；DP 枚举所有子情况取最优，更稳妥但慢。
拔高18最长回文子串一般用什么 DP 状态？
dp[i][j]：子串 i~j 是否回文，按长度从小到大填。
⑪ 记忆口诀 + 7 天复习计划
三句口诀
① 两特征：最优子结构 + 重叠子问题。
② 四步：定状态、写转移、定初值、从底填表。
③ 背包选不选、LCS 相等加 1，备忘录别重复算。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，理解爬楼梯 | 会推 dp[n] |
| 第 2 天 | 背四步 + 基础 1-6 | 说清两特征 |
| 第 3 天 | 做中档 7-12 | 手推背包表 |
| 第 4 天 | 做拔高 13-18 | 懂空间优化 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 3 分钟 |
| 第 6-7 天 | 合上书口述三句口诀 | 不看资料全说对 |
← 返回算法与AI总览