04 动态规划

本章对应考试中的：P1 矩阵链乘（2011期末，20 分）、P2 最长公共子序列 LCS（多版本，15～20 分）、P3 投资分配（2011影印）、P4 生产-库存计划（2012影印/2013）、P5 货车分配（2020）、P6 货物分销（merged）、P7 公路广告牌（样题1/试卷3）。
动态规划（DP）是本课程分值最高、最容易拿满分的大题。原因是：它的作答格式是完全固定的，资源分配类题目更是"换个数字的同一道题"。本章目标——让你能默写模板、能把表格手工填出来。

核心考点

动态规划（dynamic programming，简称 DP）：把一个大问题拆成一系列小问题（子问题），从最小的子问题开始、把每个子问题的答案算出来存进一张表，后面要用就查表，从而避免重复计算，最终拼出大问题的答案。

考试考两种 DP 大题：

资源分配型（P3 投资、P4 生产库存、P5 货车、P6 货物）：把有限的资源（钱、产量、车、货）分给若干对象，求总收益最大或总成本最小。这四道题是同一个模板的换皮，是性价比最高的考点。
经典型（P1 矩阵链乘、P2 LCS、P7 广告牌）：每道有自己特定的状态转移方程，但作答框架一样。

所有 DP 大题的得分点都是固定的五样：状态变量、决策变量、状态转移方程、边界条件、手工填表过程。把这五样写全写对就能拿大头分。

从零开始的前置知识

为什么需要"存表"——重复子问题

先看一个不存表会出大问题的例子。斐波那契数定义为 $F (n) = F (n - 1) + F (n - 2)$ ，边界 $F (1) = F (2) = 1$ 。如果直接照定义递归计算 $F (5)$ ：

算 $F (5)$ 要算 $F (4)$ 和 $F (3)$ ；
算 $F (4)$ 又要算 $F (3)$ 和 $F (2)$ ；
算 $F (3)$ 又要算 $F (2)$ 和 $F (1)$ ……

你会发现 $F (3)$ 被重复计算了， $F (2)$ 被算了更多次。规模一大，重复次数呈指数增长，总计算量达到 $O (2^{n})$ 量级。

DP 的解决办法：开一张表 $F [1. . n]$ ，从 $F [1]$ 、 $F [2]$ 开始往后逐个填， $F [i] = F [i - 1] + F [i - 2]$ 。每个 $F [i]$ 只算一次，总共 $n$ 步，复杂度降到 $O (n)$ 。这就是判断题里说的"动态规划通过增加空间复杂性来降低时间复杂性"（用一张表的空间，换掉重复计算的时间）。

DP 和分治的区别

分治（详见 02_分治算法.md）也把大问题拆成子问题，但分治的子问题互不相干（例如归并排序左右两半独立），所以不需要存表。DP 的子问题会互相重叠（像上面 $F (3)$ 被多处用到），所以必须存表。判断一道题用不用 DP，关键就看子问题会不会重复出现。

什么是"最优子结构"

最优子结构（optimal substructure）：大问题的最优解里，包含了它的子问题的最优解。只有具备这个性质，DP 才能用"子问题最优"拼出"大问题最优"。本章所有题都具备这个性质，作答时不必证明，知道这个词的意思即可。

核心理论与方法

动态规划通用四步模板（必背）

任何 DP 大题，按下面四步写，再加手工填表，就齐全了。

第 1 步：设状态变量

状态变量：描述"当前局面"所需要的那几个量。资源分配类题目，状态通常是两样合一："现在轮到第几个对象"+"手上还剩多少资源"。

写法示例："设阶段 $k$ 表示正在考虑第 $k$ 个对象（项目／月份／公司／零售店）；状态 $s$ 表示此刻还可分配的资源数量。"

第 2 步：设决策变量

决策变量：这一步你要做的选择。

写法示例："设决策 $u$ 表示分配给第 $k$ 个对象的资源量，取值范围 $0 \leq u \leq s$ 。"

第 3 步：写状态转移方程

状态转移方程（state transition equation）：用"子问题的最优值"表示"当前问题的最优值"的等式，是 DP 的核心。资源分配类的通用形式（以求最大收益为例）：

f_{k} (s) = max_{0 \leq u \leq s} {g_{k} (u) + f_{k + 1} (s - u)}

逐符号解释：

$f_{k} (s)$ ：从第 $k$ 个对象开始往后、手上有 $s$ 份资源时，能取得的最优总收益。这是我们要填进表里的值。
$g_{k} (u)$ ：给第 $k$ 个对象分配 $u$ 份资源带来的直接收益（直接查题目给的收益表）。
$f_{k + 1} (s - u)$ ：把剩下的 $s - u$ 份资源留给后面对象，能取得的最优收益（这是已经算好、存在表里的子问题答案）。
$max_{0 \leq u \leq s}$ ：在所有可能的分配量 $u$ 里，挑使括号内总和最大的那个。

如果题目是求最小成本，就把 $max$ 换成 $min$ ，把 $g_{k} (u)$ 换成成本即可。

第 4 步：写边界条件

边界条件：递推的起点。

写法示例："边界 $f_{n + 1} (s) \equiv 0$ （没有对象可分配时，收益为 $0$ ）。"

第 5 步：手工填表（采分关键）

从边界出发，逆着对象顺序（先算最后一个对象的表 $f_{n}$ ，再 $f_{n - 1}$ ，……最后 $f_{1}$ ），每个表把每个状态 $s$ 对应的 $f_{k} (s)$ 算出来，并记下取到最优时的决策 $u$ 。最后从 $f_{1}$ 开始正向回溯，读出每个对象实际分了多少。这一步必须把计算过程写出来，只写最终答案不给分。

一个最小的演示例子

为了把模板讲透，先做一个最简单的：有 3 万元投给 2 个项目，求最大利润。 收益表（投 $u$ 万元的利润）：

投资额 $u$	0	1	2	3
项目 1 收益 $g_{1} (u)$	0	4	7	9
项目 2 收益 $g_{2} (u)$	0	5	8	10

阶段 $k \in {1, 2}$ ；状态 $s$ = 剩余资金；决策 $u$ = 投给项目 $k$ 的钱；转移 $f_{k} (s) = max_{0 \leq u \leq s} {g_{k} (u) + f_{k + 1} (s - u)}$ ；边界 $f_{3} (s) \equiv 0$ 。

先算 $f_{2}$ （最后一个项目， $f_{2} (s) = max_{0 \leq u \leq s} {g_{2} (u) + 0} = max_{0 \leq u \leq s} g_{2} (u)$ ，因为 $g_{2}$ 递增，取 $u = s$ ）：

$s$	0	1	2	3
$f_{2} (s)$	0	5	8	10
最优 $u_{2}$	0	1	2	3

再算 $f_{1} (3)$ （手上 3 万，要在项目 1 投 $u$ 、剩下给项目 2）：

f_{1} (3) = max {\begin{cases} u = 0 : & g_{1} (0) + f_{2} (3) = 0 + 10 = 10 \\ u = 1 : & g_{1} (1) + f_{2} (2) = 4 + 8 = 12 \\ u = 2 : & g_{1} (2) + f_{2} (1) = 7 + 5 = 12 \\ u = 3 : & g_{1} (3) + f_{2} (0) = 9 + 0 = 9 \end{cases} = 12.

最大利润 12 万元，在 $u_{1} = 1$ （项目 1 投 1 万）时取到，此时剩 2 万给项目 2（ $f_{2} (2)$ 在 $u_{2} = 2$ 取到）。所以最优方案：项目 1 投 1 万、项目 2 投 2 万，利润 $4 + 8 = 12$ 。

下面四道资源分配大题（P3～P6）就是把"对象个数"和"收益表"换一换，方法一模一样。

答题模板

【状态变量】设阶段 k = 第 k 个对象；状态 s = 当前剩余资源。
【决策变量】设 u = 分配给第 k 个对象的资源量，0 ≤ u ≤ s。
【状态转移方程】f_k(s) = max/min_{0≤u≤s} { g_k(u) + f_{k+1}(s-u) }。
【边界条件】f_{n+1}(s) ≡ 0。
【手工求解】从 f_n 逆序逐表计算（写出每个 max/min 的每一项），到 f_1；
            再从 f_1 正向回溯，读出每个对象分到多少。
【结果】最优值 = ___，最优方案 = ___。
【复杂度】状态数 × 每状态决策数 = O(___)。

逐题精解

P1 矩阵链乘最优结合（`2011期末`，20 分）

原题：写出用动态规划求矩阵链乘积 $A_{l + 1} \times \dots \times A_{h}$ 的递推公式、伪代码和时间复杂性，并手工计算 $d = A_{3, 4} \times A_{4, 6} \times A_{6, 1} \times A_{1, 5}$ 的最优策略与最小开销（ $A_{x, y}$ 表示 $x \times y$ 阶矩阵）。

前置：两个矩阵相乘的代价。 一个 $x \times y$ 的矩阵乘一个 $y \times z$ 的矩阵，结果是 $x \times z$ 矩阵，需要做 $x \cdot y \cdot z$ 次数乘法。例如 $A_{3 \times 4} \times B_{4 \times 6}$ 要 $3 \times 4 \times 6 = 72$ 次乘法。

为什么加括号顺序会影响总代价。 矩阵连乘满足结合律，结果一样，但乘法次数不同。以 $A_{3, 4} \times A_{4, 6} \times A_{6, 1}$ 为例：

先算前两个： $(A_{3, 4} \times A_{4, 6}) \times A_{6, 1}$ ，代价 $3 \cdot 4 \cdot 6 + 3 \cdot 6 \cdot 1 = 72 + 18 = 90$ 。
先算后两个： $A_{3, 4} \times (A_{4, 6} \times A_{6, 1})$ ，代价 $4 \cdot 6 \cdot 1 + 3 \cdot 4 \cdot 1 = 24 + 12 = 36$ 。

同样的结果，代价相差一倍多。DP 的任务就是找出代价最小的加括号方式。

递推公式。 用 $m [l, h]$ 表示把第 $l$ 到第 $h$ 个矩阵连乘起来的最小乘法次数。维数记为数组 $d = [d_{0}, d_{1}, \dots, d_{n}]$ ，第 $i$ 个矩阵是 $d_{i - 1} \times d_{i}$ 阶。

m [l, h] = {\begin{cases} 0 & l = h (只有一个矩阵，不用乘) \\ min_{l \leq i < h} {m [l, i] + m [i + 1, h] + d_{l - 1} d_{i} d_{h}} & l < h \end{cases}

逐符号解释： $m [l, i]$ 是左半段 $A_{l} \dots A_{i}$ 的最小代价， $m [i + 1, h]$ 是右半段 $A_{i + 1} \dots A_{h}$ 的最小代价， $d_{l - 1} d_{i} d_{h}$ 是把左右两个结果（ $d_{l - 1} \times d_{i}$ 与 $d_{i} \times d_{h}$ ）合并相乘的代价； $i$ 是"最后一次乘法的分界点"，在所有可能的分界点里取最小。

伪代码：

text

MatrixChain(d[0..n]):
    for l ← 1 to n: m[l][l] ← 0          // 单个矩阵代价为 0
    for len ← 2 to n:                    // 链长从 2 到 n
        for l ← 1 to n-len+1:
            h ← l+len-1
            m[l][h] ← ∞
            for i ← l to h-1:            // 枚举分界点
                cost ← m[l][i] + m[i+1][h] + d[l-1]*d[i]*d[h]
                if cost < m[l][h]:
                    m[l][h] ← cost
                    s[l][h] ← i          // 记录最优分界点，便于回溯加括号
    return m[1][n], s

时间复杂性： 有 $O (n^{2})$ 个 $m [l, h]$ 要算，每个要枚举 $O (n)$ 个分界点，故 $O (n^{3})$ 。

手工计算（ $d = [3, 4, 6, 1, 5]$ ，即 $A_{1} = 3 \times 4, A_{2} = 4 \times 6, A_{3} = 6 \times 1, A_{4} = 1 \times 5$ ）。

链长 2：

m [1, 2] = d_{0} d_{1} d_{2} = 3 \cdot 4 \cdot 6 = 72, m [2, 3] = d_{1} d_{2} d_{3} = 4 \cdot 6 \cdot 1 = 24, m [3, 4] = d_{2} d_{3} d_{4} = 6 \cdot 1 \cdot 5 = 30.

链长 3：

m [1, 3] = min {\begin{cases} i = 1 : & m [1, 1] + m [2, 3] + d_{0} d_{1} d_{3} = 0 + 24 + 3 \cdot 4 \cdot 1 = 36 \\ i = 2 : & m [1, 2] + m [3, 3] + d_{0} d_{2} d_{3} = 72 + 0 + 3 \cdot 6 \cdot 1 = 90 \end{cases} = 36 (i = 1) .

m [2, 4] = min {\begin{cases} i = 2 : & m [2, 2] + m [3, 4] + d_{1} d_{2} d_{4} = 0 + 30 + 4 \cdot 6 \cdot 5 = 150 \\ i = 3 : & m [2, 3] + m [4, 4] + d_{1} d_{3} d_{4} = 24 + 0 + 4 \cdot 1 \cdot 5 = 44 \end{cases} = 44 (i = 3) .

链长 4：

m [1, 4] = min {\begin{cases} i = 1 : & m [1, 1] + m [2, 4] + d_{0} d_{1} d_{4} = 0 + 44 + 3 \cdot 4 \cdot 5 = 104 \\ i = 2 : & m [1, 2] + m [3, 4] + d_{0} d_{2} d_{4} = 72 + 30 + 3 \cdot 6 \cdot 5 = 192 \\ i = 3 : & m [1, 3] + m [4, 4] + d_{0} d_{3} d_{4} = 36 + 0 + 3 \cdot 1 \cdot 5 = 51 \end{cases} = 51 (i = 3) .

把这些值填进表（行 $l$ 、列 $h$ ，只填上三角）：

$m [l, h]$	$h = 1$	$h = 2$	$h = 3$	$h = 4$
$l = 1$	0	72	36	51
$l = 2$		0	24	44
$l = 3$			0	30
$l = 4$				0

回溯加括号： $m [1, 4]$ 在 $i = 3$ 取到 → 切成 $(A_{1} A_{2} A_{3}) (A_{4})$ ； $m [1, 3]$ 在 $i = 1$ 取到 → 切成 $(A_{1}) (A_{2} A_{3})$ 。合起来：

((A_{3, 4} \times (A_{4, 6} \times A_{6, 1})) \times A_{1, 5}), 最小开销 = 51.

易错点：① 合并代价是 $d_{l - 1} d_{i} d_{h}$ ，三个下标别取错（左段行数、分界点列数、右段列数）；② 必须从短链往长链算，因为长链要用到短链的结果。

P2 最长公共子序列（LCS，多版本）

原题：写出用动态规划求两序列最长公共子序列的递推公式、伪代码和时间复杂性，并手工计算给定序列的 LCS。

前置：子序列 vs 子串。 子序列（subsequence）：从原序列里按原顺序挑出若干字符（可以不连续）。例如 ace 是 abcde 的子序列。子串（substring）：必须是连续的一段。例如 bcd 是子串，bd 不是子串但是子序列。LCS 求的是公共子序列（两个序列都包含的、可不连续的最长那个）。

递推公式。 设两序列 $X = x_{1} x_{2} \dots x_{m}$ 、 $Y = y_{1} y_{2} \dots y_{n}$ ， $c [i, j]$ 表示 $X$ 前 $i$ 个字符与 $Y$ 前 $j$ 个字符的 LCS 长度：

c [i, j] = {\begin{cases} 0 & i = 0 或 j = 0 \\ 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}

逐符号解释：当两个当前字符相同（ $x_{i} = y_{j}$ ），LCS 在"去掉这两个字符"的基础上加 1；当不同，就看"去掉 $x_{i}$ "和"去掉 $y_{j}$ "两种情况里哪个 LCS 更长。

伪代码：

text

LCS(X[1..m], Y[1..n]):
    for i ← 0 to m: c[i][0] ← 0
    for j ← 0 to n: c[0][j] ← 0
    for i ← 1 to m:
        for j ← 1 to n:
            if X[i] == Y[j]: c[i][j] ← c[i-1][j-1] + 1
            else:            c[i][j] ← max(c[i-1][j], c[i][j-1])
    return c[m][n]

时间复杂性： 表有 $m \times n$ 个格子，每个 $O (1)$ ，故 $O (m n)$ 。

版本 A 手工计算（来源 样题2 试卷2，15 分）： $X =$ abcbcc， $Y =$ cacbac。

按递推逐格填表（行是 $X$ 的字符，列是 $Y$ 的字符）：

	c	a	c	b	a	c
$\emptyset$	0	0	0	0	0	0
a	0	1	1	1	1	1
b	0	1	1	2	2	2
c	1	1	2	2	2	3
b	1	1	2	3	3	3
c	1	1	2	3	3	4
c	1	1	2	3	3	4

右下角 $c [6, 6] = 4$ ，即 LCS 长度为 4。

回溯求出具体 LCS：从右下角出发，相等就取该字符并往左上走，不等就往值大的方向走（上或左）：

$(6, 6)$ ：c=c → 取 c，走到 $(5, 5)$ ；
$(5, 5)$ ：c≠a，上下相等取上 → $(4, 5)$ ； $(4, 5)$ ：b≠a → 往左 $(4, 4)$ ；
$(4, 4)$ ：b=b → 取 b，走到 $(3, 3)$ ；
$(3, 3)$ ：c=c → 取 c，走到 $(2, 2)$ ；
$(2, 2)$ ：b≠a → 往上 $(1, 2)$ ； $(1, 2)$ ：a=a → 取 a，走到 $(0, 1)$ 结束。

逆序拼起来得 LCS = acbc（长度 4）。

其它版本结果（方法完全相同，自行填表即可）：

版本 B（样题1/试卷1/试卷3）： $X =$ xzyzzyx， $Y =$ zxyyzxz → LCS 长度 5。
版本 C（试卷4，20 分，要求写出全过程）： $X =$ xzyzzyx， $Y =$ zxyyzxzy → LCS 长度 5，如 xyzzy 或 zyzzy。

易错点：① 第 0 行、第 0 列要先填 0；② 回溯时若上、左值相等，选哪个都行，可能得到不同但等长的 LCS。

P3 投资分配（`2011影印`，8 分）

原题：8 万元投给 3 个项目，各项目在不同投资额下的利润见下表，求总利润最大的投资计划（写出状态变量、决策变量、状态转移方程与递推关系式，及手工求解步骤与结果）。

投资额（万元）	1	2	3	4	5	6	7	8
项目 1 $g_{1}$	5	15	40	80	90	95	98	100
项目 2 $g_{2}$	5	15	40	60	70	73	74	75
项目 3 $g_{3}$	4	26	40	45	50	51	52	53

【状态/决策/方程】 阶段 $k$ = 项目编号（1,2,3）；状态 $s$ = 还可投资的金额；决策 $u$ = 投给项目 $k$ 的金额。转移方程

f_{k} (s) = max_{0 \leq u \leq s} {g_{k} (u) + f_{k + 1} (s - u)}, f_{4} (s) \equiv 0.

【手工求解】

第一张表 $f_{3} (s)$ （最后一个项目，直接取 $g_{3}$ 的最大，因 $g_{3}$ 递增即 $u = s$ ）：

$s$	0	1	2	3	4	5	6	7	8
$f_{3} (s)$	0	4	26	40	45	50	51	52	53

第二张表 $f_{2} (s) = max_{0 \leq u \leq s} {g_{2} (u) + f_{3} (s - u)}$ （只需算到 $s = 8$ ）。以 $f_{2} (8)$ 为例展示算法：

f_{2} (8) = max {0 + 53, 5 + 52, 15 + 51, 40 + 50, 60 + 45, 70 + 40, 73 + 26, 74 + 4, 75 + 0} = 110.

（上面九项分别对应给项目 2 投 $u = 0, 1, \dots, 8$ 。最大 110 在 $u = 5$ 。）逐个算出整张表：

$s$	0	1	2	3	4	5	6	7	8
$f_{2} (s)$	0	5	26	40	60	70	86	100	110
最优 $u_{2}$	0	1	0	0/3	4	5	4	4	5

第三张表只需 $f_{1} (8)$ ：

f_{1} (8) = max_{0 \leq u \leq 8} {g_{1} (u) + f_{2} (8 - u)} = max {0 + 110, 5 + 100, 15 + 86, 40 + 70, 80 + 60, 90 + 40, 95 + 26, 98 + 5, 100 + 0} = 140 .

最大值 140 在 $u_{1} = 4$ 取到。

【回溯】 $u_{1} = 4$ （项目 1 投 4，收益 80）→ 剩 4 → $f_{2} (4)$ 在 $u_{2} = 4$ 取到（项目 2 投 4，收益 60）→ 剩 0 → 项目 3 投 0。

【结果】 最大总利润 = 140 万元，方案：项目 1 投 4 万、项目 2 投 4 万、项目 3 投 0 万（ $80 + 60 + 0 = 140$ ）。

P4 生产-库存计划（`2012影印`/`2013`）

原题：未来四个月需求量为月1=2、月2=3、月3=2、月4=4。每月若生产，固定成本 3 千元；每生产 1 单位成本 1 千元；每月生产批量不超过 6 单位；每单位每月库存费 0.5 千元；第 1 月初与第 4 月末均无库存。求总成本最低的生产与库存安排。

【状态/决策/方程】 阶段 $k$ = 月份（1～4）；状态 $s_{k}$ = 第 $k$ 月月初库存；决策 $u_{k}$ = 第 $k$ 月生产量， $0 \leq u_{k} \leq 6$ 。

库存递推： $s_{k + 1} = s_{k} + u_{k} - d_{k}$ （ $d_{k}$ 是第 $k$ 月需求），且必须 $s_{k} + u_{k} \geq d_{k}$ （不能缺货）。
单月成本： ${cost}_{k} = 3 \cdot [u_{k} > 0] + 1 \cdot u_{k} + 0.5 \cdot s_{k + 1}$ 。其中 $[u_{k} > 0]$ 表示"生产了就记 1、没生产记 0"（固定成本只在生产时发生）； $0.5 \cdot s_{k + 1}$ 是月末库存的存储费。
转移方程（求最小）： $f_{k} (s_{k}) = min_{u_{k}} {{cost}_{k} + f_{k + 1} (s_{k + 1})}$ 。
边界： $s_{1} = 0$ ，要求 $s_{5} = 0$ ，故 $f_{5} (0) = 0$ 。

【一个关键观察，帮你检查答案】 因为月初、月末库存都为 0，总生产量恒等于总需求 $= 2 + 3 + 2 + 4 = 11$ ，所以"按单位算的生产成本"恒为 $11 \times 1 = 11$ ，与方案无关。于是真正要优化的只有：固定成本 $3 \times (生产的月数)$ 加上库存费 $0.5 \times (各月末库存之和)$ 。

【手工求解（逆序填表）】 状态 $s_{k}$ 的取值范围有限（库存不会超过后续总需求）。逐表计算：

$f_{4} (s_{4})$ （第 4 月，必须把库存清零，故 $u_{4} = 4 - s_{4}$ ）：

$s_{4}$	0	1	2	3	4
$u_{4}$	4	3	2	1	0
$f_{4} (s_{4})$	7	6	5	4	0

（例： $s_{4} = 0$ 时 $u_{4} = 4$ ，成本 $3 + 4 + 0 = 7$ ； $s_{4} = 4$ 时 $u_{4} = 0$ 不生产，成本 0。）

$f_{3} (s_{3})$ （ $d_{3} = 2$ ， $f_{3} (s_{3}) = min_{u_{3}} {3 [u_{3} > 0] + u_{3} + 0.5 s_{4} + f_{4} (s_{4})}$ ， $s_{4} = s_{3} + u_{3} - 2$ ）：

$s_{3}$	0	1	2	3	4	5	6
$f_{3} (s_{3})$	11	10	7	6.5	6	5.5	2
最优 $u_{3}$	6	5	0	0	0	0	0

（例： $f_{3} (0)$ 取 $u_{3} = 6$ → $s_{4} = 4$ ：成本 $3 + 6 + 0.5 \cdot 4 = 11$ ，加 $f_{4} (4) = 0$ ，共 11。）

$f_{2} (s_{2})$ （ $d_{2} = 3$ ， $s_{3} = s_{2} + u_{2} - 3$ ）：

$s_{2}$	0	1	2	3	4
$f_{2} (s_{2})$	16	15	14	11	10.5
最优 $u_{2}$	5	4	3	0	0

（例： $f_{2} (3)$ 取 $u_{2} = 0$ → $s_{3} = 0$ ：成本 0，加 $f_{3} (0) = 11$ ，共 11。）

$f_{1} (0)$ （ $d_{1} = 2$ ， $s_{1} = 0$ ，必须生产 $u_{1} \geq 2$ ）：

f_{1} (0) = min_{2 \leq u_{1} \leq 6} {3 + u_{1} + 0.5 s_{2} + f_{2} (s_{2})}, s_{2} = u_{1} - 2.

$u_{1}$	2	3	4	5	6
$s_{2} = u_{1} - 2$	0	1	2	3	4
当月成本 $3 + u_{1} + 0.5 s_{2}$	5	6.5	8	9.5	11
$+ f_{2} (s_{2})$	16	15	14	11	10.5
合计	21	21.5	22	20.5	21.5

最小 20.5 在 $u_{1} = 5$ 取到。

【回溯】 $u_{1} = 5$ → $s_{2} = 3$ → $f_{2} (3)$ 取 $u_{2} = 0$ → $s_{3} = 0$ → $f_{3} (0)$ 取 $u_{3} = 6$ → $s_{4} = 4$ → $f_{4} (4)$ 取 $u_{4} = 0$ 。

【结果】 最低总成本 = 20.5 千元，生产策略：月 1 生产 5、月 2 生产 0、月 3 生产 6、月 4 生产 0（靠库存覆盖月 2、月 4 的需求）。验证：固定成本 $3 \times 2 = 6$ + 生产成本 11 + 库存费 $0.5 \times (3 + 0 + 4 + 0) = 3.5$ ，合计 $20.5$ 。✓

P5 货车分配（`2020`，5 分）

原题：5 台货车分给 A、B、C 三个子公司，各公司分到不同车数的年利润见下表，求总利润最大的分配。

车辆数	A	B	C
0	0	0	0
1	2	5	5
2	6	9	6
3	10	11	11
4	11	12	12
5	13	12	13

【方程】 阶段 = 子公司（A,B,C），状态 $s$ = 剩余车辆， $f_{k} (s) = max_{0 \leq u \leq s} {g_{k} (u) + f_{k + 1} (s - u)}$ ， $f_{D} \equiv 0$ 。

【关键表】 逆序算 $f_{C}$ （=各车数下 C 的利润，递增取 $u = s$ ）、 $f_{B}$ 、 $f_{A} (5)$ ：

$s$	0	1	2	3	4	5
$f_{C} (s)$	0	5	6	11	12	13
$f_{B} (s)$	0	5	10	14	16	20

f_{A} (5) = max {0 + f_{B} (5), 2 + f_{B} (4), 6 + f_{B} (3), 10 + f_{B} (2), 11 + f_{B} (1), 13 + f_{B} (0)} = max {20, 18, 20, 20, 16, 13} = 20 .

【结果】 最大总利润 = 20。存在多个并列最优解，例如：A=0、B=2、C=3（ $0 + 9 + 11 = 20$ ）；A=2、B=2、C=1（ $6 + 9 + 5 = 20$ ）；A=3、B=1、C=1（ $10 + 5 + 5 = 20$ ）。任写一个即可。

P6 货物分销（`merged`，8 分）

原题：一车 6 箱货沿途卸到 4 个零售店，各店卸下不同箱数的利润见下表，求总利润最大的卸货方案。

箱数 \ 店	1	2	3	4
1	4	2	3	4
2	6	4	5	5
3	7	6	7	6
4	7	8	8	6
5	7	9	8	6
6	7	10	8	6

【方程】 阶段 = 零售店 $k$ （1～4），状态 $s_{k}$ = 到第 $k$ 店时剩余箱数（ $s_{1} = 6$ ），决策 $u_{k}$ = 在第 $k$ 店卸下的箱数， $f_{k} (s_{k}) = max_{0 \leq u_{k} \leq s_{k}} {v_{k} [u_{k}] + f_{k + 1} (s_{k} - u_{k})}$ ， $f_{5} \equiv 0$ 。

【结果】 按逆序填表（ $f_{4} \to f_{3} \to f_{2} \to f_{1} (6)$ ）求得 最大总利润 = 17，存在多种并列最优卸货方案，例如 $(1, 1, 3, 1)$ 、 $(2, 2, 1, 1)$ 、 $(2, 1, 2, 1)$ 等（验证 $(1, 1, 3, 1)$ ： $4 + 2 + 7 + 4 = 17$ ）。

P7 公路广告牌（`样题1`/`试卷3`）

原题：一条由西到东长 $M$ 公里的公路，可设广告牌的地点为 $x_{1}, \dots, x_{n}$ （已知各点坐标），各点放牌收益 $p_{1}, \dots, p_{n}$ ，要求任两块广告牌距离不小于 3 公里，求总收益最大的放置方案。

【思路】 先把地点按坐标从西到东排序。对每个地点 $i$ ，定义 $p r e v (i)$ = 满足 $x_{j} \leq x_{i} - 3$ 的最大下标 $j$ （即"在 $i$ 西边、与 $i$ 至少隔 3 公里"的最后一个可放点）。设 $f (i)$ = 只考虑前 $i$ 个地点时的最大总收益。每个地点只有"放"或"不放"两种选择：

f (i) = max {\underset{第 i 点不放}{\underset{⏟}{f (i - 1)}}, \underset{第 i 点放}{\underset{⏟}{p_{i} + f (p r e v (i))}}}, f (0) = 0.

逐符号解释：不放第 $i$ 点，收益就是前 $i - 1$ 点的最优 $f (i - 1)$ ；放第 $i$ 点，收益是它的 $p_{i}$ 加上"必须隔开 3 公里之外"的 $f (p r e v (i))$ （因为 $p r e v (i)$ 之后到 $i$ 之间的点都离 $i$ 太近不能再放）。答案是 $f (n)$ 。

【小例子】 设地点坐标 $x = [0, 2, 4, 6]$ 、收益 $p = [5, 6, 3, 7]$ 。则 $p r e v$ ： $p r e v (1) = 0$ （前面没有点）， $p r e v (2) = 0$ （ $x_{1} = 0 \leq 2 - 3 = - 1$ ? 否，故 0）， $p r e v (3)$ ：要 $x_{j} \leq 4 - 3 = 1$ ，只有 $x_{1} = 0$ ，故 $p r e v (3) = 1$ ； $p r e v (4)$ ：要 $x_{j} \leq 6 - 3 = 3$ ， $x_{1} = 0, x_{2} = 2$ 满足，最大下标 2，故 $p r e v (4) = 2$ 。

$f (0) = 0$ ； $f (1) = max {0, 5 + f (0)} = 5$ ；
$f (2) = max {f (1) = 5, 6 + f (0) = 6} = 6$ ；
$f (3) = max {f (2) = 6, 3 + f (1) = 8} = 8$ ；
$f (4) = max {f (3) = 8, 7 + f (2) = 13} = 13$ 。

最大收益 13（放第 2 点和第 4 点： $6 + 7 = 13$ ，坐标 2 与 6 相距 4≥3，合法）。

【复杂度】 地点已排序时，用双指针求所有 $p r e v (i)$ 是 $O (n)$ ，填表 $O (n)$ ，总 $O (n)$ ；若用二分查找求 $p r e v$ 则 $O (n \log n)$ ；若还要先排序则排序 $O (n \log n)$ 主导。

高频陷阱 / 易错点小结

四步模板不能漏：状态、决策、转移方程、边界，缺一个扣一块分；手算过程必须写，光写答案不给分。
求最小成本时把 $max$ 换成 $min$ （P4），别套错方向。
填表顺序：资源分配类逆着对象顺序算（先 $f_{n}$ 后 $f_{1}$ ）；矩阵链乘从短链到长链算；LCS 从左上到右下。顺序错了会用到还没算出的值。
P4 固定成本只在"生产量大于 0"时计入，不生产的月份不算这 3 千元。
多个最优解（P5、P6）很常见，写出任意一个并验证总和正确即可。
回溯方案别忘做：题目要"安排计划"，只给最优值不给方案会扣分。

自测清单

[ ] 不看书默写"动态规划通用四步模板"（状态/决策/转移方程/边界）。
[ ] 说清 DP 与分治的区别（子问题是否重叠、要不要存表）。
[ ] 独立把 P3 投资分配的三张表填出来，得到 140 与方案。
[ ] 独立把 P4 生产库存做出来，得到 20.5 与生产策略 $(5, 0, 6, 0)$ 。
[ ] 写出矩阵链乘的递推式，并把 $d = [3, 4, 6, 1, 5]$ 算到最优 51。
[ ] 写出 LCS 递推式，把版本 A 的表填出来并回溯出 acbc。
[ ] 写出广告牌的递推式并解释 $p r e v (i)$ 的含义。

04 动态规划 ​

核心考点 ​

从零开始的前置知识 ​

为什么需要"存表"——重复子问题 ​

DP 和分治的区别 ​

什么是"最优子结构" ​

核心理论与方法 ​

动态规划通用四步模板（必背） ​

第 1 步：设状态变量 ​

第 2 步：设决策变量 ​

第 3 步：写状态转移方程 ​

第 4 步：写边界条件 ​

第 5 步：手工填表（采分关键） ​

一个最小的演示例子 ​

答题模板 ​

逐题精解 ​

P1 矩阵链乘最优结合（2011期末，20 分） ​

P2 最长公共子序列（LCS，多版本） ​

P3 投资分配（2011影印，8 分） ​

P4 生产-库存计划（2012影印/2013） ​

P5 货车分配（2020，5 分） ​

P6 货物分销（merged，8 分） ​

P7 公路广告牌（样题1/试卷3） ​

高频陷阱 / 易错点小结 ​

自测清单 ​