（xc）动态规划

官官方信息技术老师·13 页·深入（追求细节与边界）·0 次浏览·3 天前
✦ （xc）动态规划信息技术（xc）动态规划: 动态规划
状态设计转移方程优化技巧边界讨论

（xc）动态规划

一张图谱看懂DP：状态怎么设、转移怎么写、优化怎么做

按 空格/→ 演示下一步

1 / 13 页

全部页面点击任意一页，跳回舞台从这页播放

状态设计转移方程优化技巧边界讨论

（xc）动态规划

一张图谱看懂DP：状态怎么设、转移怎么写、优化怎么做

1第 1 页 · （xc）动态规划

: 动态规划

爬楼梯时每步可跨 1 或 2 级，到第 N 级有几种走法？暴力递归会发现同一个子问题被反复算几百次——动态规划正是为消除这种浪费而生。

最优子结构
问题的最优解可由子问题的最优解拼出
重叠子问题
不同路径会反复撞上同一个子问题
状态与转移方程
用 f[i] 描述局面，写出递推式
填表或记忆化
自底向上递推，或递归时缓存结果
爬楼梯时记小本本对应 →动态规划的记忆化

第一次算出第 k 级的走法就写下来，下次再问直接翻本子，不再重新爬

f[i]=f[i−1]+f[i−2]f[i] = f[i-1] + f[i-2]
2第 2 页 · : 动态规划

: Fib()：递推方程

上页我们确认了 DP 的两个特征：最优子结构和重叠子问题。现在用最小、最经典的例子把它们落到纸上——Fibonacci 递推方程。

递推方程
F(n) = F(n-1) + F(n-2)，第 n 项等于前两项之和
边界条件
F(0)=0, F(1)=1，是递推的起点，没有它方程无解
状态定义
F(n) 表示第 n 个 Fibonacci 数，是 DP 要存的子问题
重叠子问题
朴素递归会重复算同一个 F(k) 无数次，是需要记忆化的原因
走楼梯每次跨 1 或 2 级对应 →Fib 递推方程

到第 n 阶的方式数 = 到 n-1 阶 + 到 n-2 阶之和，和 Fib 同构

F(n)=F(n−1)+F(n−2),F(0)=0, F(1)=1F(n) = F(n-1) + F(n-2),\quad F(0)=0,\ F(1)=1
3第 3 页 · : Fib()：递推方程

: Fib()：封底估算

递推方程写出来了，可它到底有多慢？不必真跑程序——'封底估算'就是在纸背几秒估出量级，这是判断要不要优化的第一步。

封底估算
只看数量级秒判复杂度，不求精确常数
调用树指数级
递归每层节点约翻倍，n 层规模即 ~2^n
重复子问题
同一 Fib(k) 被左右子树各算一次，浪费根源
结论对照
朴素 O(2^n) vs 备忘 O(n)，差好几个量级
心算存款多少年翻倍对应 →心算 Fib(n) 调用次数

都用粗略量级，不算到分；72 法则与 2^n 同思路

Tnaive(n)∼2n→TDP(n)=nT_{\text{naive}}(n) \sim 2^n \quad\to\quad T_{\text{DP}}(n) = n
4第 4 页 · : Fib()：封底估算

: Fib()：递归跟踪

上一页写了 Fib() 的递推方程，但它只是一个等式。真的去执行 Fib(5)，会展开成怎样的调用树？同一层里出现了几次 F(2)、F(3)？这一页把递归过程摊开来看。

递归调用树
每次 Fib(n) 向下分裂出 Fib(n-1)、Fib(n-2) 两支，n 步后形成二叉树
同一子问题被反复求解
Fib(3) 在 Fib(5) 中被算 2 次、Fib(2) 被算 3 次，越往下重复越多
调用次数满足同一递推
T(n)=T(n-1)+T(n-2)+1 与 F(n) 形态相同，因此 T(n)=Θ(φⁿ)
n 稍大就不可承受
φ≈1.618，Fib(40)≈10⁸ 次调用，Fib(50) 已是千亿级别
家族族谱里同一祖先被反复统计对应 →递归树里同一子问题被反复求解

越靠近根的子问题，所在分支越多，被算的次数也越多——冗余随树深指数膨胀

T(n)=T(n−1)+T(n−2)+1⇒T(n)=Θ(φn)T(n)=T(n-1)+T(n-2)+1\Rightarrow T(n)=\Theta(\varphi^n)
5第 5 页 · : Fib()：递归跟踪

: Fib()：迭代

上一页看到 fib(3) 被算了两次——重复计算是最贵的浪费。迭代换个方向：从 fib(1)、fib(2) 开始往上垒,每步只看前两项。

反向递推
从 fib(1)、fib(2) 开始自底向上推,而不是从 fib(n) 自顶向下挖
滚动变量
只保留前两项 prev 和 curr,每轮用前两项之和算下一项
状态压缩
无需 O(n) 数组存全部中间值,两个变量就够——空间从 O(n) 降到 O(1)
时空复杂度
每个 F(i) 只算一次,共 n 次加法:O(n) 时间、O(1) 空间
爬楼梯只看脚下两级对应 →迭代递推

不用记住走过的每一级台阶,只要看前两级就能算出下一级

(a,b)→(b, a+b)(a,b)\to(b,\,a+b)
6第 6 页 · : Fib()：迭代

: 最长公共子序列

Fib() 是一维递推——状态只跟一个下标挂钩。LCS 把它推到二维：dp[i][j] 表示两个前缀的 LCS 长度，依赖左上、上、左三个方向。这是 1D 到 2D DP 的标志性推广。

子序列定义
保持原顺序即可，不要求连续——和子串的关键差异
状态定义
dp[i][j] = X 前 i 字符与 Y 前 j 字符的 LCS 长度
递推方程
字符相同则左上+1，否则取上/左的最大值
路径重建
从右下往左上回溯，按决策方向还原出实际序列
边界与复杂度
第 0 行/列=0；时间 O(mn)，空间可压到 O(min(m,n))
两份文档的 diff对应 →LCS

未修改的行串就是公共子序列，diff 工具正是基于 LCS

dp[i][j]={dp[i−1][j−1]+1,Xi=Yjmax⁡(dp[i−1][j],  dp[i][j−1]),Xi≠Yjdp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & X_i = Y_j \\ \max(dp[i-1][j],\; dp[i][j-1]), & X_i \neq Y_j \end{cases}
7第 7 页 · : 最长公共子序列

: LCS：递归

Fib() 递归一句话就能写完：F(n)=F(n-1)+F(n-2)。LCS 要分情况——末尾字符相等还是不等？相等怎么走、不等又怎么走？这页给出完整的递推式。

子问题
LCS(i,j) 是 X 前 i 个字符与 Y 前 j 个字符的 LCS 长度
三条分支
末位等走对角（+1），不等走「缩 X」或「缩 Y」（取较大）
递归基
任一序列为空时 LCS = 0
指数级代价
朴素递归重复求解同一 (i,j)，调用次数随 n+m 指数爆炸
两本书目录对比对应 →LCS 递归

从末章往前翻，章名相同则两本都回翻；不同则只让其中一本回翻一章

LCS(i,j)={0i=0 or j=0LCS(i−1,j−1)+1Xi=Yjmax⁡(LCS(i−1,j),LCS(i,j−1))otherwiseLCS(i,j) = \begin{cases} 0 & i=0 \text{ or } j=0 \\ LCS(i-1,j-1)+1 & X_i = Y_j \\ \max(LCS(i-1,j), LCS(i,j-1)) & \text{otherwise} \end{cases}
8第 8 页 · : LCS：递归

: LCS：理解

你用过 git diff 吗？它怎么精准告诉你『哪些行没动』？不是逐字比，而是找出『依然在两边按顺序出现』的片段——这就是最长公共子序列（LCS）。

子序列不是子串
可以跳着取，不必连续。'ACE' 是 'ABCDE' 的子序列
DP 递推
字符相等则左上 +1，否则取上 / 左的最大值
复杂度 O(mn)
填一张 m×n 表，每格 O(1)，共 m·n 格
典型应用
git diff、DNA 比对、论文查重、输入法候选
git diff 找保留段对应 →LCS 找最长公共子序列

新版删掉的部分，就是 LCS 之外被切掉的字符

c[i,j]={c[i−1,j−1]+1xi=yjmax⁡(c[i−1,j], c[i,j−1])xi≠yjc[i,j] = \begin{cases} c[i-1,j-1]+1 & x_i=y_j \\ \max(c[i-1,j],\,c[i,j-1]) & x_i \neq y_j \end{cases}
9第 9 页 · : LCS：理解

: LCS：复杂度

上页我们用递推把 LCS 拆成格子之间的依赖。这页回到老问题：这套解法到底跑多快？能不能像 Fib 那样砍掉指数爆炸？

时间 O(n·m)
两序列长度 n、m，递推共算 n×m 格，每格 O(1)
对比 Fib 递推
从指数 O(2ⁿ) 砍到多项式 O(n·m)，正是 DP 的威力
空间 O(n·m)
朴素版需存整张表；滚动数组可压到 O(min(n,m))
压缩原理
每行算完即可丢弃，只需保留两行来回轮换
Excel 求和对应 →DP 状态转移

每格只引用左、上、左上三格即可算出

T(n,m)=O(n⋅m)T(n,m) = O(n \cdot m)
10第 10 页 · : LCS：复杂度

: LCS：动态规划

前一页看到，朴素递归会反复计算相同后缀；把“已经算过的最长长度”保存下来，递推就从重复枚举变成逐格填表。关键是每个格子代表什么、依据哪条规则更新。

问题定义
LCS 只要求元素按相同相对顺序出现，不要求在两序列中连续。
状态 c[i][j]
表示 A 前 i 项与 B 前 j 项的最长公共子序列长度。
递推决策
末项相同：左上值加 1；末项不同：上方与左方取最大。
边界与顺序
空前缀为 0；i、j 递增，让左、上、左上先就绪；并列时任选方向。
还原与应用
从右下角回溯可还原一个 LCS；并列分支选哪条都可；模型用于版本比较、文本相似度与 DNA 比对。
逐项核对两版合同对应 →LCS 动态规划

相同条款沿左上推进并加一；不同则选上方或左方较长，而且不要求条款连续。

c[i][j]={0,i=0∨j=0c[i−1][j−1]+1,Ai=Bjmax⁡(c[i−1][j],c[i][j−1]),Ai≠Bjc[i][j]=\begin{cases}0,&i=0\lor j=0\\c[i-1][j-1]+1,&A_i=B_j\\\max(c[i-1][j],c[i][j-1]),&A_i\ne B_j\end{cases}
11第 11 页 · : LCS：动态规划

本节要点

  • ✓DP的本质：用空间换时间，消除重叠子问题的重复计算
  • ✓递推方程的成立需要识别最优子结构与重叠子问题
  • ✓迭代常比递归更省空间——Fib()只需两个滚动变量
  • ✓复杂度先于代码：子问题数 × 单步代价 = 总成本
  • ✓边界条件是DP最易出错的环节，需逐一验证
延伸主题：编辑距离：LCS的加权推广区间DP与状态压缩DP的常数级优化技巧
12第 12 页 · 本节要点

课后思考

先自己写下思路，再点开参考答案对照——题目没有标准答案。

1为什么递归版Fib()是指数级，迭代版却线性？本质差在哪？

参考答案递归版重复求解大量子问题；迭代版自底向上填值，每个子问题只算一次。根本在于有没有复用子问题的解。

2现实中有哪些问题天然适合用LCS建模？试着举两三个场景。

参考答案DNA序列比对找最长匹配片段；论文查重找最长公共句段；git diff 本质也是求最长公共子序列。

3如果两个序列里某元素反复出现，DP还能保证最优吗？

参考答案能。LCS不要求元素唯一，DP状态只与两序列前缀长度有关，与元素出现频次解耦，重复元素不影响最优性。

13第 13 页 · 课后思考