2026年秋第7次课

周子力大约 12 分钟教学文档算法设计与分析课程讲义动态规划线性DP区间DP

2026年秋第7次课

本课围绕使用最小花费爬楼梯和矩阵连乘，讨论同一个问题：状态定义怎样决定动态规划的形状？

第4次课已经看到，快速幂把同一个半次幂求两次就会退化成线性时间，复用子问题结果才得到对数时间。本次课把这一点推进到最优化问题：先想清楚「最后一步发生了什么」，再决定状态需要几个下标、按什么顺序计算、答案从哪里取。两道题看似一简一繁，实际是从一维状态跨到二维状态的一级台阶。各题的完整 Python 实现、执行过程和课堂练习见对应题目链接。

学习目标

会建模： 能说清 dp[i] 与 dp[i][j] 分别表示什么，并解释为什么矩阵连乘不能只用一个下标。
会推导： 能从「最后一次决策」写出两道题的状态转移方程，并指出各自依赖哪些更小的状态。
会核对： 能判断递推顺序是否合法，验证边界与答案取值，说明时间、辅助空间以及计数模型。
会迁移： 能把「按区间长度递推」用于石子合并等同构问题，并识别什么时候需要记录决策以恢复方案。

本课路线

本次课按 2 学时 90 分钟组织，学生动手与核对时间不少于三分之一。

环节	时间	内容	课堂产出
问题热身	8′	爬楼梯计数加费用，辨析「站在台阶不付费、离开才付费」	说清顶部下标与起点
方法精讲一	20′	使用最小花费爬楼梯：两套状态定义、贪心反例、边界	写出转移方程
现场编码	15′	Python 主实现、滚动变量、边界用例测试	跑通两个官方示例
方法精讲二	30′	矩阵连乘：括号方案代价对比、区间状态、按长度填表	手算 4 矩阵 dp 表
课堂核对	12′	完成下方 5 道核对题，重点检查递推顺序与代价下标	口头解释错误写法
复盘小结	5′	方法比较表、易错清单、课后每日两题	形成一页总结

s 表回溯与最优括号输出留作课后阅读矩阵连乘，课上只要求得到最少乘法次数。题目文档以 3 个矩阵 p=[10,30,5,60]（最少 4500 次）为贯穿示例，并配有按区间长度填表的交互动画；本讲义另外增加一个 4 矩阵示例，用于展示长度 2、3、4 三层递推。

分析每道题时，依次回答以下五个问题：

状态表示什么？ 是一个位置，还是一段区间。
最后一次决策是什么？ 从哪一步爬到顶，或在哪个位置加最后一对括号。
依赖哪些更小的状态？ 固定两个前驱，还是所有更短的子区间。
按什么顺序算？ 保证用到的状态已经算好，说明为什么其他顺序不行。
答案与方案从哪里取？ 只取一个最优值，还是需要用决策表恢复完整方案。

题目顺序：

使用最小花费爬楼梯：一维线性 DP，把边界和状态含义彻底讲清。
矩阵连乘：二维区间 DP，状态维度、决策数量和递推顺序同时变化。

题目串联

一使用最小花费爬楼梯把最后一步写成状态

详细题解与代码：使用最小花费爬楼梯。

题意有三处容易读错：cost[i] 是从第 i 阶离开时支付的费用，站在台阶上不付费；可以从下标 0 或 1 起步，这两处也不付费；cost 长度为 $n$ 时，楼梯顶部的下标是 $n$ ，不是 $n-1$ 。

到达顶部 $n$ 的最后一步只有两种：从 $n-1$ 爬 1 阶，或从 $n-2$ 爬 2 阶。于是定义：

dp[i]=\min\bigl(dp[i-1]+cost[i-1],\ dp[i-2]+cost[i-2]\bigr),\qquad dp[0]=dp[1]=0,

其中 $dp[i]$ 表示到达第 i 阶、尚未支付 cost[i] 的最小花费，答案为 $dp[n]$ 。

以 cost = [10, 15, 20] 为例：

i	0	1	2	3（顶部）
dp[i]	0	0	min(0+15, 0+10) = 10	min(10+20, 0+15) = 15

答案是 15，即从下标 1 起步、支付 15 后一次跨两阶到顶。

两套等价定义不能混用

另一种常见写法是令 $f[i]$ 表示到达第 i 阶且已支付 cost[i] 的最小花费：

f[i]=cost[i]+\min(f[i-1],f[i-2]),\qquad f[0]=cost[0],\ f[1]=cost[1],

答案为 $\min(f[n-1],f[n-2])$ 。

两套定义互为反向，都是正确的。差别在于 $dp[i]$ 不含 $cost[i]$ 、答案取 $dp[n]$ ； $f[i]$ 含 $cost[i]$ 、答案取最后两项的较小者。把其中一套的转移方程配上另一套的答案，或把第一套判定为错误设计，都是错的。这是本次课要纠正的第一个概念点，也是学生提交中最常见的错误来源。

为什么不能用贪心

同一示例中，从下标 0 起步只需先付 10，比从下标 1 起步付 15 更便宜；但沿这条路必须再付 20，总花费 30，反而更贵。局部最便宜的一步不保证全局最优，因此要保留「从 i-1 来」和「从 i-2 来」两种可能再取较小值。

若直接按转移式写递归，每个状态会重复展开成两个分支，时间为 $O(2^n)$ ；自底向上填表把每个状态只算一次，时间降为 $O(n)$ ，且 $dp[i]$ 只依赖前两项，可用两个滚动变量把辅助空间压到 $O(1)$ 。这与第4次课快速幂「重复计算会退化」是同一个道理。

衔接矩阵连乘： 这里的状态只用一个下标，决策固定为两个前驱。如果最优解必须同时记住「从哪一个矩阵到哪一个矩阵」，一个下标还够用吗？

二矩阵连乘状态从位置变成区间

详细题解与代码：矩阵连乘。

给三个矩阵 $A_1(10\times30)$ 、 $A_2(30\times5)$ 、 $A_3(5\times60)$ ，矩阵乘法满足结合律，两种括号次序的代价差异很大：

括号方案	第一步	第二步	标量乘法总数
$((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

相差 6 倍。 $n$ 个矩阵的完全加括号方案数是第 $n-1$ 个 Catalan 数， $n=10$ 时已有 4862 种，穷举不可行。

设 $A_i$ 的维数为 $p_{i-1}\times p_i$ 。无论中间怎样加括号，计算 $A_i\cdots A_j$ 的最后一次乘法一定在某个分割点 $k$ 处，把结果分成 $(A_i\cdots A_k)$ 与 $(A_{k+1}\cdots A_j)$ 两部分相乘。前者结果为 $p_{i-1}\times p_k$ ，后者为 $p_k\times p_j$ ，这次相乘的代价是 $p_{i-1}p_kp_j$ 。因此：

dp[i][j]=\min_{i\leq k<j}\Bigl(dp[i][k]+dp[k+1][j]+p_{i-1}p_kp_j\Bigr),\qquad dp[i][i]=0.

$dp[i][j]$ 表示计算 $A_i\cdots A_j$ 的最少标量乘法次数，答案为 $dp[1][n]$ 。代价里的 $p_{i-1}$ 、 $p_k$ 、 $p_j$ 分别取自整个区间的左端、分割点和右端，不是子区间局部的维数，这是最容易写错的一处。

用 4 个矩阵手算填表

课堂扩展示例取 $p=[10,30,5,60,20]$ ，即 $A_1(10\times30)$ 、 $A_2(30\times5)$ 、 $A_3(5\times60)$ 、 $A_4(60\times20)$ ；它比题目文档的 3 矩阵示例多一层长度 4 的递推。

区间长度	区间	候选 k 与代价	最优值	分割点
2	$[1,2]$	$10\cdot30\cdot5$	1500	1
2	$[2,3]$	$30\cdot5\cdot60$	9000	2
2	$[3,4]$	$5\cdot60\cdot20$	6000	3
3	$[1,3]$	k=1: 9000+18000 = 27000；k=2: 1500+3000 = 4500	4500	2
3	$[2,4]$	k=2: 6000+3000 = 9000；k=3: 9000+36000 = 45000	9000	2
4	$[1,4]$	k=1: 9000+6000 = 15000；k=2: 1500+6000+1000 = 8500；k=3: 4500+12000 = 16500	8500	2

最优括号方案为 $((A_1A_2)(A_3A_4))$ ：两侧各花 1500 与 6000，最后合并花 $10\cdot5\cdot20=1000$ ，合计 8500。注意胜出的是「平衡分割」k=2，而不是让某一步最省的分割。

为什么必须按区间长度递推

计算 $dp[i][j]$ 时需要 $dp[i][k]$ 和 $dp[k+1][j]$ ，两者都是更短的区间，但后者的左端点比 $i$ 更大。若按 $i$ 从 1 到 $n$ 递增、再枚举 $j$ ，会引用尚未计算的状态；只有按长度 $L=2,3,\dots,n$ 从小到大、同长度内再枚举左端点，才能保证所有依赖已就绪。这就是「无后效性」在计算顺序上的体现，也是区间 DP 与线性 DP 最本质的操作差异。

课上只要求得到 $dp[1][n]$ 。若要输出括号方案，需在每次更新时把最优的 $k$ 记入决策表 $s[i][j]$ ，再递归打印；这部分见题目文档，留作课后阅读。

三从一维到二维三处变化

变化	使用最小花费爬楼梯	矩阵连乘
状态	一个下标，表示到达某位置	一对下标，表示处理某区间
决策集合	固定 2 个前驱	随区间长度变化，最多 $O(n)$ 个分割点
计算顺序	位置 i 递增	区间长度 L 递增
代价来源	离开台阶时的一次费用	两段结果矩阵相乘的代价，依赖整个区间端点

三处变化都由「最后一次决策需要哪些信息」推出，而不是靠记忆模板。子问题数量从 $O(n)$ 变为 $O(n^2)$ ，每个子问题的决策数从 $O(1)$ 变为 $O(n)$ ，复杂度因此从 $O(n)$ 变为 $O(n^3)$ 。

方法比较

下面比较两题链接中本课使用的主实现。采用课程常用的单位成本模型：一次算术运算、一次比较记为常数时间；辅助空间不包含输入数组。

题目与任务	状态	依赖的更小状态	递推顺序	时间复杂度	辅助空间	恢复方案
使用最小花费爬楼梯，求最小花费	$dp[i]$	$dp[i-1]$ 、 $dp[i-2]$	i 从 2 到 n	$O(n)$	$O(1)$ （滚动变量）	需另记前驱
矩阵连乘，求最少乘法次数	$dp[i][j]$	所有更短子区间	区间长度 L 从 2 到 n	$O(n^3)$	$O(n^2)$	需另记 $s[i][j]$
对照：两题的朴素递归	同左	同左	自顶向下	指数级	递归栈	—

三点需要说清：

矩阵连乘共有 $O(n^2)$ 个区间状态，每个状态枚举 $O(n)$ 个分割点，故为 $O(n^3)$ ；不能只看三重循环，要说明子问题数与决策数。
这里统计的是标量乘法次数，不是程序实际运行时间。矩阵规模、缓存与实现语言都会影响实测结果。
若按转移式写成递归但没有记忆化，虽然能算出正确值，却把每个子区间重复求解多次，仍是指数级。递归只是实现方式，填表或记忆化才是把重叠子问题压成多项式的关键。

课堂任务

在 $dp[i]$ 表示「到达第 i 阶、尚未支付 cost[i]」的定义下，答案应该取 $dp[n]$ 、 $dp[n-1]$ 还是 $\min(dp[n-1],dp[n-2])$ ？为什么？
cost = [10, 15, 20] 时，从下标 0 起步第一步更便宜，为什么答案不是沿这条路走下去？
矩阵连乘中，若把合并代价写成 $p_i p_k p_j$ 会错在哪里？请以 $dp[1][3]$ 为例说明下标应如何取。
计算 $dp[1][4]$ 时用到了 $dp[3][4]$ 。若改为按左端点 $i=1,2,3,4$ 依次计算，会出现什么问题？
$p=[10,30,5,60,20]$ 的最优值是 8500，对应括号方案是什么？请逐步核对三段代价。

参考答案

取 $dp[n]$ 。顶部下标是 $n$ ， $dp[n]$ 已经包含「从 $n-1$ 支付 cost[n-1] 爬 1 阶」和「从 $n-2$ 支付 cost[n-2] 爬 2 阶」两种情况。 $\min(dp[n-1],dp[n-2])$ 属于另一种状态定义（ $f[i]$ 含 cost[i]）的答案，混用会算错。
从 0 起步付 10 到 2 阶后，仍需支付 cost[2]=20 才能到顶，总计 30；从 1 起步付 15 一次跨两阶即可到顶，总计 15。局部最省不能决定全局最优，所以必须比较两种来路。
$p_i$ 不是区间 $[i,j]$ 左结果的维数。区间 $A_i\cdots A_j$ 左结果的行数是 $p_{i-1}$ ，右结果的列数是 $p_j$ ，分割点处共有维数 $p_k$ ，故代价是 $p_{i-1}p_kp_j$ 。以 $dp[1][3]$ 、 $p=[10,30,5,60,20]$ 的 k=2 为例，代价为 $p_0p_2p_3=10\cdot5\cdot60=3000$ ；若误写为 $p_1p_2p_3=30\cdot5\cdot60=9000$ ，就会把 4500 错算成 10500。
$dp[3][4]$ 的左端点 3 大于 1，按左端点递增时它排在 $dp[1][4]$ 之后才算，此时 $dp[1][4]$ 会读到未计算（或初值）的状态。按区间长度递推保证所有长度小于 L 的区间先算完。
$((A_1A_2)(A_3A_4))$ 。 $A_1A_2$ 花 $10\cdot30\cdot5=1500$ ， $A_3A_4$ 花 $5\cdot60\cdot20=6000$ ，两个结果 $10\times5$ 与 $5\times20$ 相乘花 $10\cdot5\cdot20=1000$ ，合计 8500。

课后每日两题： A 层完成爬楼梯与题目文档中的基础核对题；B 层用石子合并迁移「按区间长度递推」，并写出状态、转移、递推顺序和复杂度。

相关导学：算法概览、动态规划的分类。