深入理解动态规划（一）

前言

由于自己写过很多次动态规划，还是容易忘记，只有专题刷的时候，才有手感，因此这次从原理出发，准备好好理解一下这个思想。

背景

动态规划的来源

• 时间背景：动态规划最早由美国数学家 Richard Bellman 在 1950 年代提出。
• 动机：当时在运筹学（Operations Research）和国防决策问题中，经常需要解决“如何在一系列决策中，找到整体最优解”的问题。
  • 例如：一架飞机要从 A 飞到 B，中途可能要加油，怎样选择加油站能让总花费最少？
  • 或者：工厂如何安排生产计划，让总收益最大？

Bellman 发现：这些问题都有一个特点——

大问题可以分解为若干个 子问题，而且子问题之间存在 重叠。

他提出了一个核心思想：
最优子结构（optimal substructure） + 重叠子问题（overlapping subproblems） = 可以用动态规划解决。

“规划”？

当时 Bellman 用了“programming”这个词，其实不是“编程”的意思，而是指“规划/计划”。所以 Dynamic Programming 翻译成中文就是“动态规划”，意思是“随着时间推进，逐步做出最优决策的规划方法”。

核心要素

从经典问题斐波那契数列出发，一步步思考核心思想。

问题：

F(n) = F(n-1) + F(n-2)，其中 F(1)=1, F(2)=1。

第一步：直觉解法

最直观的方法是写递归：

1

F(n) = F(n-1) + F(n-2)

但是这样会产生大量重复计算。比如 F(5) 需要 F(4) 和 F(3)，而 F(4) 又会再算一次 F(3)。

很自然的可以认为，这里面是可以优化的，对于每次的计算，我们可以保留结果。

第二步：能不能复用子问题结果？

如果我把已经算过的 F(3) 存起来，那么后面再需要 F(3) 时，直接用现成答案就行。

这就是“保存子问题的解”能提高效率。

第三步：想一想问题的结构

F(n) 的解，其实就是由 F(n-1) 和 F(n-2) 组合而成。
换句话说：

• 大问题 F(n) 的解 = 小问题 F(n-1)、F(n-2) 的解。

第四步：推导

由以上三步可知，对于某类问题，我们可以利用一些数据结构去保存其中的子问题，最自然的办法是：

• 开一个数组 dp[i]，表示 F(i) 的值。
• 然后依次推导：

1
2

dp[1] = 1, dp[2] = 1
dp[i] = dp[i-1] + dp[i-2]  (i>=3)

通过思考斐波那契，我们自然总结出：

1. 发现子问题会被重复使用 → 重叠子问题
2. 发现大问题依赖于小问题的解 → ？
3. 为了保存子问题结果，我们给它们起名字（dp[i]） → 状态表示
4. 我们需要一个公式来描述子问题之间的关系（dp[i] = dp[i-1] + dp[i-2]） → 状态转移方程

但我们依然没得到一个关键点，对于其中大问题依赖小问题的解，定义还是很含糊。

在斐波那契里，我们看到的是：

• F(5) 可以由 F(4) 和 F(3) 得到
• F(4) 又可以由 F(3) 和 F(2) 得到

这说明：大问题的答案可以从小问题的答案组合出来。这里还没有“最优”的意味，仅仅是可分解。

如果问题是：从 1 楼走到 n 楼，每次可以走 1 或 2 步，问有多少种走法？

• 到第 n 楼的方法 = 到 (n-1) 楼的方法数 + 到 (n-2) 楼的方法数。
  这其实和斐波那契一模一样。

但是，如果问题换成：
从 1 楼走到 n 楼，每次可以走 1 或 2 步，但我想用最少的步数走完。

• 那么，走到第 n 楼的最优解 = min(走到 n-1 楼的最优解 + 1, 走到 n-2 楼的最优解 + 1)。

这时我们看到：大问题的最优解，是由小问题的“最优解”推出来的。此时我们才能归纳出所谓的最优子结构

其实 斐波那契数列 这个例子，本质上并 没有“最优”的味道，它只是展示了“分解 + 重叠”的思想。
所以很多教材用斐波那契引入 DP，只是因为它足够简单、容易看出“子问题重叠”。

但严格来说，它只能说明“子问题分解”，而不是“最优子结构”。因此我认为斐波那契数列仅是递推思考，而非真正的动态规划。

递推or动态规划？

广义的动态规划

• 只要有 状态表示 和 状态转移，就可以算作动态规划。
• 斐波那契数列、爬楼梯问题，都符合这种定义。
• 在这种意义下，递推就是最简单的 DP。

狭义的动态规划

• 更强调它解决的是 最优性问题（最短路径、最大收益、最小代价……）。
• 所以斐波那契数列算不上严格的“最优问题”，只能说是 DP 的“启蒙练习”。

递推 = 动态规划的一部分（特别是最基础的部分）。而动态规划的全部思想，比单纯的递推更广，它还要考虑 “最优子结构”。

总结

动态规划的真正要素：

1. 发现子问题会被重复使用 → 重叠子问题

2. 如果一个问题的最优解，可以由它的子问题的最优解直接推出，也就是我们的最优子结构。

3. 为了保存子问题结果，我们需要数据结构来存储结果，一般是数组。俗称 状态表示

4. 为了用数学公式描述子问题的关系，我们需要列出状态转移方程