2026年秋第6次课

面对许多可选方案，怎样只保存必要的信息，就能得到整体最优解？

上一次课讨论了快速排序的划分、木材加工的单调判定，以及最长公共前缀的摘要合并。本课转入动态规划：从打家劫舍的“选或不选”，到矩阵连乘的“最后一次在哪里分开”，再到最大子数组和的“接上前段还是重新开始”，重点训练状态定义、转移推导与计算顺序。

本讲义按三个题目串联课堂思路，完整题目材料见对应链接。课堂先画依赖、推导关系，再检查边界和复杂度；不把记住某个公式作为理解算法的替代。

学习目标

本课需要回答的五个问题

• 状态表示什么？ 用一句完整的话定义状态，明确它是否必须包含某个位置。
• 最后一步有哪些选择？ 将所有合法方案分成可穷尽的情况，说明各分支怎样使用子问题结果。
• 为什么只保存最优值就够？ 证明替换为更优的子方案后，当前方案仍然合法。
• 按什么顺序计算？ 先计算被依赖的状态，避免读取尚未求出的结果。
• 结果在哪里，成本是多少？ 区分状态值与最终答案，按状态数和每个状态的转移成本分析效率。

课后应能独立写出三题的状态、边界、转移和答案位置，并能通过小规模过程表核对结果。

本课路线

顺序	题目与材料入口	课堂核心问题	状态的形状
1	打家劫舍	当前房屋选或不选，怎样保持不相邻？	一个前缀上的最优值
2	矩阵连乘	最后一次相乘可以在哪个位置断开？	一个闭区间上的最优值
3	最大子数组和	为了保持连续，之前必须保留什么信息？	强制以当前位置结尾的最优值

三个题目依次推进：先学习从两种选择得到递推，再学习在区间中枚举切分点，最后检验状态是否足以支持下一步。虽然打家劫舍与最大子数组和都可以用一维数组实现，它们的状态含义与答案位置并不相同。

题目串联

一、打家劫舍：用前缀最优值处理相邻约束

题目材料：打家劫舍。

明确本课的线性模型

给定沿直线排列的房屋，金额为非负整数列表 nums，相邻房屋不能同时选择，求可选择的最大总金额。允许不选任何房屋，空列表返回0。本课只要求最优金额，不要求输出房屋编号方案。

为方便讲解，房屋编号使用1到 $n$，第 $i$ 间房屋的金额记为 $v_i$，对应 Python 中的 nums[i - 1]。首间与末间是否相邻，由排列模型决定：直线排列中，只有编号相差1的两间房屋相邻。

例如 [2, 7, 9, 3, 1] 可以选第1、3、5间，总金额为12。不能只选当前金额最大的房屋就断言最优：[2, 3, 2] 中，选中间的3只能得到3，选两端则得到4。

区分直线与环形

本课与题解中的 Python 实现均采用直线模型。若将问题拆成“去掉末间”和“去掉首间”两种情况再取最大值，解决的是首尾也相邻的环形扩展，应先明确新增的首尾约束。

可用 [2, 1, 1, 2] 检验：直线模型可以选第1、4间，答案为4；环形模型不允许首尾同时选择，答案为3。两种模型不能共用同一个答案。

从最后一间房屋推导转移

定义 $F(i)$：前 $i$ 间房屋中，满足不相邻约束时能选择的最大总金额。 这个状态不要求一定选择第 $i$ 间。

边界为：

$$F(0)=0,\qquad F(1)=v_1\quad(n\geq1).$$

对 $i\geq2$，根据是否选择第 $i$ 间，将全部合法方案分成两类：

最后一次决策	剩余部分的约束	本类能达到的最大金额
不选第 $i$ 间	只需在前 $i-1$ 间中选	$F(i-1)$
选择第 $i$ 间	第 $i-1$ 间不能选，只能搭配前 $i-2$ 间	$F(i-2)+v_i$

因此：

$$F(i)=\max\bigl(F(i-1),\ F(i-2)+v_i\bigr).$$

这两类覆盖所有合法方案，取最大值即可。选择第 $i$ 间时，前 $i-2$ 间中任何合法方案都能与它搭配，因此可直接使用该前缀的最优值；不需要保留每一种历史选择。

注意，算法没有规定“只选奇数编号”或“只选偶数编号”。例如 [2, 1, 1, 2] 的最优方案同时包含奇数编号1与偶数编号4。

先列状态表，再考虑空间优化

对 [2, 7, 9, 3, 1]，按房屋数量从小到大计算：

前缀长度 $i$	当前金额 $v_i$	不选当前房屋	选择当前房屋	$F(i)$
0	—	—	—	0
1	2	0	2	2
2	7	2	$0+7=7$	7
3	9	7	$2+9=11$	11
4	3	11	$7+3=10$	11
5	1	11	$11+1=12$	12

最终答案就是 $F(n)$。这里的表先帮助理解全部状态；计算最优金额时，只依赖前两个状态，可以进一步改用两个滚动变量。

普通递归在求 $F(i-1)$ 和 $F(i-2)$ 的过程中，会反复求解同一前缀。记忆化递归在再次遇到状态时读取缓存，自底向上则按 $0,1,\ldots,n$ 的顺序计算，每个状态只需求一次。

按照整数加法与比较为单位成本，时间为 $O(n)$；保存整个状态表的辅助空间为 $O(n)$，仅求金额的滚动变量版本为 $O(1)$。更新滚动变量时必须先使用旧的两个状态求出新值，再移动变量，避免覆盖仍需使用的信息。

衔接矩阵连乘： 打家劫舍只需区分“选或不选”。如果当前问题的最后一步可以在许多位置切分，状态与转移需要怎样改变？

二、矩阵连乘：枚举最后一次相乘的切分点

题目材料：矩阵连乘。

先明确改变的是括号，而不是矩阵顺序

给定按顺序相乘的 $n\geq1$ 个矩阵 $A_1,A_2,\ldots,A_n$，维度数组为正整数序列 $p_0,p_1,\ldots,p_n$，其中 $A_i$ 的大小为 $p_{i-1}\times p_i$。

矩阵乘法满足结合律，因此可以改变括号与计算先后，但不能任意交换矩阵的位置。本课采用普通矩阵乘法的标量乘法次数作为成本：一个 $a\times b$ 矩阵乘以一个 $b\times c$ 矩阵，需要 $abc$ 次标量乘法。

目标是求最少标量乘法次数，并说明如何记录切分点以恢复一种最优括号方案。这里计算的是运算计划，不需要读入矩阵元素，也不实际完成矩阵乘法。

取维度数组 [10, 30, 5, 60]：

方案	第一次相乘	最后一次相乘	总成本
$(A_1A_2)A_3$	$10\times30\times5=1500$	$10\times5\times60=3000$	4500
$A_1(A_2A_3)$	$30\times5\times60=9000$	$10\times30\times60=18000$	27000

两种方案的结果维度都是 $10\times60$，但标量乘法次数差别很大。

用最后一次相乘定义区间状态

定义 $M(i,j)$：按原顺序计算矩阵链 $A_i\cdots A_j$ 的最少标量乘法次数。 矩阵编号从1开始，使用闭区间 $[i,j]$。

只有一个矩阵时，不需要乘法：

$$M(i,i)=0.$$

对 $i<j$，任意一种完全加括号方案的最后一次相乘，都可以在某个 $k$ 处分开：

$$(A_i\cdots A_k)(A_{k+1}\cdots A_j),\qquad i\leq k<j.$$

无论两侧内部如何加括号，左侧结果维度总为 $p_{i-1}\times p_k$，右侧结果维度总为 $p_k\times p_j$。最后一次相乘的成本因此固定为 $p_{i-1}p_kp_j$，得到：

$$M(i,j)=\min_{i\leq k<j} \left\{M(i,k)+M(k+1,j)+p_{i-1}p_kp_j\right\}.$$

固定切分点后，如果一侧使用了更贵的子方案，可以将它替换为该子链的最优方案：结果维度不变，后续相乘仍然合法，总成本只会降低或不变。这证明了使用两侧最优值的依据。再枚举所有合法切分点，就不会漏掉整体最优括号方案。

按区间长度填表

转移依赖的都是更短区间，因此先填长度1，再填长度2，依次直到长度 $n$。不能随意按行填表，否则可能读到尚未计算的状态。

对上述三个矩阵，计算顺序如下：

区间长度	状态	切分及候选成本	状态值
1	$M(1,1),M(2,2),M(3,3)$	单矩阵无须相乘	均为0
2	$M(1,2)$	$0+0+10\times30\times5$	1500
2	$M(2,3)$	$0+0+30\times5\times60$	9000
3	$M(1,3)$	$k=1$：$0+9000+10\times30\times60=27000$	比较后取4500
3	同一状态的另一候选	$k=2$：$1500+0+10\times5\times60=4500$	记录切分点2

用 $S(i,j)$ 保存取得最小值时的切分点；若有多个最优点，可以按约定保留其中一个。恢复括号时，在 $S(i,j)$ 处分开，依次恢复两侧；到单矩阵时输出其编号。题解中的 Python 实现用显式栈组织这一遍历，本例恢复为 $((A_1A_2)A_3)$。

写入结果表，还不等于避免重复计算

自底向上的区间动态规划，或计算前先检查缓存的记忆化递归，才能让每个区间状态只求一次。题解中的 Python 主实现按区间长度填表，保证转移时依赖的短区间已经计算；若改用普通递归却不读取缓存，就不能直接套用 $O(n^3)$ 时间结论。

分清计划成本与算法运行成本

共有 $n(n+1)/2$ 个有效区间，每个区间至多枚举 $O(n)$ 个切分点，因此求最优计划的时间为 $O(n^3)$。成本表与切分表各占 $O(n^2)$ 空间。这里把维度整数的乘法、加法与比较视为单位成本。

4500是示例最优计划执行时的标量乘法次数；$O(n^3)$ 是寻找最优计划的时间复杂度，二者描述不同的任务。恢复括号时，若遍历切分树、收集符号后一次拼接，只需访问 $O(n)$ 个节点。按一个矩阵标号或括号为一个输出符号计，输出与遍历栈各至多占 $O(n)$；实际字符串字符数的分析见题解，不改变整体动态规划的复杂度上界。

衔接最大子数组和： 状态可以覆盖一个前缀，也可以覆盖一个区间。但只说“前面已经得到最大值”是否总够用？当题目要求连续时，能否把前缀中的最优结果直接接到当前元素上？

三、最大子数组和：先限定结尾，才能保持连续

题目材料与 Python 实现：最大子数组和。

为什么“前缀中的最大和”不够支持直接延伸

给定非空整数列表，求和最大的连续子数组，子数组至少包含一个元素，可以有负数。子数组必须连续，不能跳过中间的元素。

若只记住前缀中出现过的最大子数组和，该子数组不一定紧接当前元素。例如 [-5, 4, -1, 2]，处理最后的2之前，前缀最大和为4；直接加2得到6，相当于跳过了中间的 -1，不合法。正确的最大和为 $4-1+2=5$。

因此，需要定义一个能够合法接上当前元素的状态。

定义必须包含当前位置的状态

列表下标从0开始，记元素为 $a_i$。定义 $D(i)$：必须以位置 $i$ 结尾的非空连续子数组的最大和。

以位置 $i$ 结尾的子数组只有两类：它只包含当前元素，或者它由一个以 $i-1$ 结尾的非空子数组接上当前元素得到。因此：

$$D(0)=a_0,\qquad D(i)=\max\bigl(a_i,\ D(i-1)+a_i\bigr)\quad(i\geq1).$$

在第二类中，所有候选都增加相同的 $a_i$，所以只需保留之前最大的结尾状态，其他较小候选不会变得更优。这是丢弃历史方案的依据。

当前状态不一定是全局答案。再用 $B(i)$ 表示前缀 $[0,i]$ 中任意非空连续子数组的最大和，则：

$$B(0)=a_0,\qquad B(i)=\max\bigl(B(i-1),D(i)\bigr).$$

最终返回 $B(n-1)$，也就是所有 $D(i)$ 的最大值；不能直接返回最后一个 $D(n-1)$。题解中的 current_sum 对应 $D(i)$，max_sum 对应 $B(i)$。

用过程表区分当前状态与历史最优

沿用题解示例 [-2, 1, -3, 4, -1, 2, 1, -5, 4]：

下标 $i$	当前元素 $a_i$	结尾状态 $D(i)$	前缀最优 $B(i)$
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

最大和为6，对应下标3到6的 [4, -1, 2, 1]。最后一个结尾状态为5，恰好说明必须另行保留历史最优。

当 $D(i-1)<0$ 时，接上这段会比从当前元素重新开始更差，因此舍弃它；当 $D(i-1)=0$ 时，两种选择的和相同，若只求最大和，任选一种即可。

非空要求决定初始化

对全负数列表 [-8, -3, -6]，答案为 -3，不能初始化全局答案为0后直接比较，否则等于允许选择空子数组。本课按非空输入讨论；题解函数对空列表返回0属于额外约定，不是非空题目的最优值。

每个位置只有常数次加法和比较，时间为 $O(n)$。保存所有结尾状态需要 $O(n)$ 辅助空间；题解的滚动版本只保存当前结尾和与全局最大和，辅助空间为 $O(1)$。

回看分治法，理解两种求解组织方式

本题也可按位置分成左右两半，最大子数组要么在左侧，要么在右侧，要么跨越分界；跨界部分由左侧最大后缀与右侧最大前缀拼成。如果每层扫描求出这两个值，就得到 $O(n\log n)$ 的分治解法。

本课的动态规划沿位置逐个处理，通过“固定结尾”避免枚举所有左右端点。更进一步，分治若同时返回总和、最大前缀和、最大后缀和与最大子数组和，也能常数时间合并、做到总时间 $O(n)$。这与上次课最长公共前缀中的“返回足够的摘要”相呼应，不能把分治法的复杂度一概写成 $O(n\log n)$。

方法比较

比较角度	打家劫舍	矩阵连乘	最大子数组和
合法性要求	相邻位置不能同时选	保持矩阵原顺序，只改变括号	选出的元素连续且非空
状态含义	前 $i$ 间中的最大金额 $F(i)$	区间矩阵链的最小成本 $M(i,j)$	必须以 $i$ 结尾的最大和 $D(i)$
最后一步	选或不选当前房屋	枚举最后一次相乘的切分点	从当前元素开始或延伸前段
转移使用的信息	前两个前缀状态	左右更短区间的成本与维度	前一个结尾状态
计算顺序	前缀长度递增	区间长度递增	元素位置递增
答案位置	$F(n)$	$M(1,n)$	所有 $D(i)$ 的最大值
时间复杂度	$O(n)$	$O(n^3)$，每个区间只求一次	$O(n)$
辅助空间	状态表 $O(n)$；滚动值 $O(1)$	成本表与切分表 $O(n^2)$	状态表 $O(n)$；滚动值 $O(1)$

三列中的 $n$ 分别表示房屋数量、矩阵数量和列表长度；上述成本按基本整数运算为单位分析。若需要输出选择方案、括号方案或子数组端点，还应另外说明记录与恢复方法，不能把“最优值”自动当作“完整方案”。

动态规划的课堂检查顺序

先把状态定义说完整，再用最后一步穷尽合法情况；证明子问题最优值足以支持当前转移，给出边界与依赖顺序，最后确定答案位置并计算成本。保存状态的目的，是复用已经求出的子问题结果；没有正确的状态与转移，单纯增加一个 dp 数组不能保证得到正确或高效的算法。

课堂任务

任务一：检验模型与选择范围

对直线房屋 [4, 1, 1, 4]，列出 $F(0)$ 到 $F(4)$，给出一个最优选择。只比较奇数编号总和与偶数编号总和，会得到多少？若改成环形，答案又是多少？

参考答案

状态依次为 0, 4, 4, 5, 8。直线模型选择第1、4间，金额为8。奇数编号与偶数编号的总和都为5，因此只比较这两种固定选择会漏掉最优方案。

环形模型中首尾相邻，不能同时选第1、4间，最大金额为5，可选第1、3间或第2、4间。

任务二：检查滚动变量更新

设处理当前房屋之前，prev2 和 prev1 分别保存前两个相关状态。为什么不能先写 prev2 = prev1，再用更新后的 prev2 计算“选择当前房屋”的候选？用 [2, 1] 核对。

参考答案

处理第2间前，prev2 = F(0) = 0、prev1 = F(1) = 2。正确的新状态为 max(2, 0 + 1) = 2。

若先覆盖 prev2，再计算 max(prev1, prev2 + 1)，会错误地得到3，相当于同时选择相邻房屋。应先用旧值计算新状态，再移动变量；Python 也可用右侧先求值的多变量赋值表达这种更新。

任务三：逐个比较矩阵链切分点

维度数组为 [5, 10, 3, 12, 5]，求四个矩阵的最优括号方案与最少标量乘法次数。先求长度2、3的区间，再比较整体区间的三个切分点。

参考答案

长度2：$M(1,2)=150$、$M(2,3)=360$、$M(3,4)=180$。

长度3：$M(1,3)=330$、$M(2,4)=330$。

整体区间的候选成本为：

切分点	候选成本
$k=1$	$0+330+5\times10\times5=580$
$k=2$	$150+180+5\times3\times5=405$
$k=3$	$330+0+5\times12\times5=630$

答案为405，一种最优方案为 $((A_1A_2)(A_3A_4))$。两侧结果分别为 $5\times3$ 与 $3\times5$，最后一次相乘需要75次标量乘法。

任务四：检查“必须结尾”与“允许为空”

分别对 [-5, 4, -1, 2] 和 [-8, -3, -6] 列出结尾状态与前缀最优值，解释为什么不能只保存前缀最优值并直接加下一个数。

参考答案

第一个列表的 $D$ 为 [-5, 4, 3, 5]，$B$ 为 [-5, 4, 4, 5]，答案为5。处理最后的2时，直接将前缀最优4与2相加会跳过 -1，破坏连续性。

第二个列表的 $D$ 为 [-8, -3, -6]，$B$ 为 [-8, -3, -3]。最后一个结尾状态是 -6，历史最优仍是 -3，最终答案为 -3；非空要求排除了空子数组的0。

任务五：从依赖关系判断计算成本

说明以下两句话的问题：“矩阵连乘有二维表，所以时间为平方级”“三个题目都取最优值，所以只需把转移中的 max 改成 min 就能互相套用”。

参考答案

二维表只说明状态数量为 $O(n^2)$；矩阵连乘每个区间还需枚举切分点，因此动态规划时间为 $O(n^3)$。如果递归没有读取缓存，同一个区间仍可能反复计算，甚至不能保证这个三次方时间上界。

max 或 min 只表达优化方向。三题的合法条件、状态、依赖与答案位置不同，必须先由题意证明转移，再决定取最大或最小，不能通过替换一个运算符互相转换。

课后实践： 用 Python 完成直线打家劫舍的状态表与滚动版本、矩阵连乘的按长度填表版本，以及最大子数组和的滚动版本。分别用空房屋列表、单矩阵、全负数子数组等边界核对；检查实际计算是否复用了状态，而不只是把结果写入数组。