完整设计一个动态规划
复习
- 动态规划从哪里来：状态与转移是核心
- 从递归到记忆化搜索：自顶向下加缓存
- 自底向上的状态转移：按依赖顺序填表
TL;DR
- 设计动态规划通常有固定几步：定状态、找转移、定边界、定顺序、求答案
- 状态定义决定了转移写起来难不难
- 有些问题还需要额外记录信息，才能还原出具体答案
- 走通一个完整例子，胜过记十条技巧
正文
前面几章讲了动态规划的原理和两种实现。这一章，我们用一个完整的例子，把“设计一个动态规划”的流程从头走一遍。
例子：最长递增子序列
问题：给一个数列，找出其中最长的、严格递增的子序列的长度（子序列不要求连续）。
比如 [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列是 [2, 3, 7, 101]，长度 4。
第一步：定义状态
这是最关键的一步。我们定义：
dp[i]：以第i个元素结尾的最长递增子序列长度。
注意这里的“以第 i 个元素结尾”很讲究。为什么不直接定义“前 i 个元素里的最长长度”？因为“以谁结尾”决定了下一个元素能不能接上去——只有知道结尾是谁，才能判断递增关系。状态里少一个信息，转移时就无从下手。
第二步：找状态转移
既然 dp[i] 是“以 i 结尾”，那它一定是从某个更早、且值比它小的元素接过来的：
dp[i] = 1 + max( dp[j] )，其中 j < i 且 a[j] < a[i]
如果前面没有比它小的，那它就自己单独成列，长度为 1。
第三步：边界与顺序
边界很自然：每个 dp[i] 至少是 1。
计算顺序：dp[i] 依赖所有 j < i，所以只要从小到大依次计算即可，依赖一定满足。
第四步：求答案
最终答案不是 dp[n]，而是所有 dp[i] 里的最大值——因为最长的子序列不一定以最后一个元素结尾。
想还原具体的序列
如果不仅想要长度，还想要那条序列本身呢？那就再记录一个前驱：每次更新 dp[i] 时，记下它是从哪个 j 接过来的。最后从最大值所在处顺着前驱回溯，就能还原出整条序列。这和前面 BFS 记录前驱还原路径是同一个套路。
走完这一遍，你会发现动态规划并不神秘：定义好状态，转移几乎是顺着写下来的。 难的是那第一步——想到一个“信息足够、又不冗余”的状态。
思考题 1
设计动态规划时，为什么“定义状态”是最关键的一步？
思考题 2
为什么有些动态规划还需要额外记录信息，才能“还原答案”？
小结
知识点
- 设计 DP 的步骤：定状态、找转移、定边界、定顺序、求答案
- 状态定义决定转移是否顺畅
- 例如最长递增子序列的状态需包含“以谁结尾”
- 记录前驱可还原具体方案
参考资料
- Wikipedia(zh)：动态规划：状态与转移的设计方法
- Wikipedia(zh)：最长递增子序列：动态规划的经典例题
思考题答案（仅供参考）
思考题 1
因为状态决定了“用什么信息描述子问题”。状态里包含的信息，直接决定了状态转移能不能写出来、难不难写。若状态缺少必要信息（如没记“以谁结尾”），就无法判断能否衔接；若信息过多，又会冗余、低效。所以状态是设计与效率的核心。
思考题 2
因为动态规划通常只记录“答案的数值”，并不记录“答案是怎么来的”。若要还原具体方案，就需要额外保存决策信息（如每个状态是从哪里转移来的），最后据此回溯，才能重建出完整解。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪