企业官网建设流程全解析

1. 一个手算的例子：括号位置不同，乘法次数差了9倍

1.1 三个矩阵，两种括号，两种代价

矩阵连乘问题用一句话讲就是：给一串连乘的矩阵，怎么加括号让计算机少做点乘法。很多初学算法的人第一次看到这个问题都觉得有点莫名其妙——乘法不就是乘法吗？先算哪两个难道还有区别？我当年在《计算理论与算法分析设计》这门课里第一次看到矩阵连乘问题，也是这么想的。直到我手算了一个小例子，才意识到这个问题的水比想象中深得多。

假设有三个矩阵：

• A1 是 10 × 20 的矩阵
• A2 是 20 × 50 的矩阵
• A3 是 50 × 1 的矩阵

连乘 A1 × A2 × A3，规则只有两个：矩阵乘法满足结合律，矩阵乘法不满足交换律。所以本质上只有两种加括号方式：

• 方式一：(A1 × A2) × A3
• 方式二：A1 × (A2 × A3)

先算方式一。A1 乘 A2，两个矩阵的尺寸是 10×20 和 20×50，得到的中间结果是 10×50。做这一次乘法需要多少次标量乘法？

10 × 20 × 50 = 10000 次。

得到中间结果后，再乘 A3（50×1），中间结果是 10×50，A3 是 50×1，做这一次乘法需要：

10 × 50 × 1 = 1000 次。

加起来，方式一总共需要 11000 次标量乘法。

再算方式二。先把 A2 和 A3 相乘，尺寸是 20×50 和 50×1，中间结果是 20×1。这一次需要的乘法次数是：

20 × 50 × 1 = 1000 次。

然后 A1（10×20）乘上中间结果（20×1），需要：

10 × 20 × 1 = 200 次。

加起来，方式二总共只要 1200 次标量乘法。

11000 对 1200，差了将近 9 倍。同一个数学表达式，只是因为括号位置不同，计算量就从一万多降到了一千多。更关键的是，这两种方式最终得到的矩阵完全一样，都是 10×1 的矩阵。这个例子直接把"矩阵连乘求最优加括号顺序"这个问题的意义敲死了：括号没加对，计算量白白翻十倍。

1.2 把问题严格化，以及"计算量"到底指什么

前面用的是最简单的三矩阵例子，现在把问题严格化。给定 n 个矩阵 A1, A2, ..., An，每个矩阵 Ai 的规模是 p[i-1] × p[i]，也就是说相邻矩阵的维度是兼容的，整个链可以连乘。要找到一种加括号方式，使得完成整个连乘所需要的标量乘法次数最少。

这里的"标量乘法"，指的是矩阵乘法中内层循环里那一次乘法操作。比如 A（m×p）乘 B（p×n），结果 C 是 m×n，一共要做 m × p × n 次标量乘法，这个数值和一次乘法的开销直接正相关。实际计算机里浮点乘法和浮点加法的开销不完全一样，但做算法分析的建模阶段，用标量乘法次数作为衡量标准已经足够接近真实情况，而且推导和比较都很方便。

于是问题的输入就变成了一个长度为 n+1 的数组 p，而不是 n 个完整的矩阵对象。矩阵本身的元素值完全不用考虑，我们关心的是它们首尾相接的尺寸序列。这个"维度数组驱动一切"的视角非常重要，很多后面要写的代码、要证的递推式，都是围绕 p 数组展开的。

要注意一个容易混淆的地方：矩阵连乘问题的最优解，关注的是运算次数，不是"存储空间"。中间结果矩阵当然也会占内存，但这在基础版问题里不是优化目标。等到实际工程里把 GPU 显存、访存带宽算进来，这个问题就会变得更复杂，后面我会单独提到。

2. 暴力为什么不行：方案数量按卡特兰数爆炸

2.1 加括号方案的计数递推

如果不知道动态规划，第一反应肯定是暴力枚举所有加括号方式，逐个算出代价，取最小。这个思路本身没错，错在方案数量增长太快。

n 个矩阵连乘，一共有多少种加括号方式？设 P(n) 表示 n 个矩阵的加括号方案数。最外层总有一个分割点，把链切成两部分，左边 i 个矩阵，右边 n-i 个矩阵，再分别对两边加括号。于是递推关系是：

P(n) = Σ(k=1, n-1) P(k) × P(n-k)

其中 P(1) = 1。这个递推式和卡特兰数的递推一模一样，算出来：

• P(1) = 1
• P(2) = 1
• P(3) = 2
• P(4) = 5
• P(5) = 14
• P(6) = 42
• P(10) = 16796
• P(15) = 2674440
• P(20) = 6564120420

到了 n=20，方案数已经超过 65 亿。就算一台机器每秒能评估一亿种方案，也要一分多钟；n 到 30，方案数超过 3.8 × 10^16，暴力枚举在工程上没有任何希望。

这里值得多讲一句：很多人记不住卡特兰数的通项公式，其实也不需要死记。你只要能从乘法结合律的角度写出上面这个递推，就能直观感受到"每多一个矩阵，括号方案数增加得更猛"。这个递推在面试里也是一个经典考点，面试官有时候不直接考矩阵连乘，而是问"n 个矩阵连乘有多少种加括号方式"，本质考的就是这个数列。

2.2 从暴力到动态规划：重叠子问题的出现

暴力枚举慢，不只是因为方案总数爆炸，更本质的原因是大量重复计算。比如在 n=5 的情况里，无论是哪一层的分割，子链 A2·A3·A4 的最小代价会被反复计算很多次。递归树展开之后，相同区间会出现在不同分支里，每次都要重新算一遍。这种结构就是教科书上说的"重叠子问题"，也是动态规划能切入的根本前提。

我当时在课堂上第一次理解到这一层时，觉得整个算法设计思维发生了变化：不需要追求"把所有方案枚举出来"，只需要保证"每个子区间只认真算一次，后面直接查表"。于是这个问题就从组合枚举问题变成了"填一张二维表"的问题。

很多人会有个疑问：为什么矩阵连乘能用区间 DP，而旅行商这种问题就不太好用？答案就在于子问题的结构。矩阵连乘的一个子链，总是原链的连续一段，任意分割后产生的两个子链仍然是连续区间，区间之间是并列关系。而很多其他组合优化问题的拆分会产生交叉依赖，没法用区间这样干净地切分。这种"切一刀变两段、两段独立求解"的模式，是区间 DP 的典型特征。

3. 动态规划建模三件套：状态、转移方程、填表顺序

3.1 状态 m[i][j] 为什么选择"区间"而不是"前缀"

很多算法题里常见的 DP 状态是"前 i 个东西怎么怎么样"，比如背包问题的 dp[i][w]。但矩阵连乘问题不一样，它不能简单用前缀来做状态。

原因在于：当你决定整个矩阵链从第 k 个矩阵后面断开时，右半部分是 Ak+1 到 An，它不是一个"以 1 开头的前缀"，而是一个从中间开始的区间。也就是说，一个问题的最优策略天然会把原链切成两段，而且两段都可能是"中间段"。反过来，如果只用前缀状态，你就必须枚举右段的终点，而右段的子问题又会切成更细的区间，最终你还是绕不开"任意连续区间"这个形态。

所以状态的定义只能是：

m[i][j] 表示计算 Ai 到 Aj 这段连续子链所需的最少标量乘法次数，其中 1 ≤ i ≤ j ≤ n。

一个特殊情况是 i = j，也就是子链只有一个矩阵，不需要做任何乘法，所以 m[i][i] = 0。这个初始化是整个 DP 的基石，几乎所有后续计算都建立在这条对角线之上。

你可以把 m[i][j] 理解成一个"关于区间的记忆单元"。整个问题最终想要的 m[1][n] 就存放在这张二维表的右上角。表里面每一格只要算一次，之后谁需要谁直接取，这就是动态规划相对暴力递归的优势。

3.2 转移方程的分割点思想

现在看 m[i][j] 怎么从更小的子问题递推出来。假设最终在 k 处断开，i ≤ k < j，即先算 Ai 到 Ak，再算 Ak+1 到 Aj，最后把两个结果矩阵乘起来。总代价就有三部分：

1. 左边子链的代价：m[i][k]；
2. 右边子链的代价：m[k+1][j]；
3. 最后那次乘法本身的代价：Ai..k 的结果矩阵和 Ak+1..j 的结果矩阵相乘需要的标量乘法次数。

第三部分怎么算？Ai 到 Ak 连乘的结果矩阵规模是 p[i-1] × p[k]，Ak+1 到 Aj 连乘的结果矩阵规模是 p[k] × p[j]，两部分相乘需要的标量乘法次数是：

p[i-1] × p[k] × p[j]

于是对于一个固定的分割点 k：

cost(i, j, k) = m[i][k] + m[k+1][j] + p[i-1] × p[k] × p[j]

最优的就是遍历所有可能的 k，取最小值：

m[i][j] = min{ m[i][k] + m[k+1][j] + p[i-1] × p[k] × p[j] }，其中 i ≤ k < j

这个转移方程看起来简单，但有三点必须反复理解：

第一，k 是分割点而不是矩阵的下标。很多人把 k 理解成"第几个矩阵处断开"，实际上 k 表示的是断在 Ak 和 Ak+1 之间。所以 k 的取值范围是 i 到 j-1，一共 j-i 个候选。

第二，最后一项里的三个 p 下标不会随着具体矩阵元素变化，它只取决于子链两端和分割点。这个形式非常整齐，写代码时只要照着 p[i-1]、p[k]、p[j] 三个位置取值就不会乱。

第三，这个转移方程天然假设了"最优子结构"。也就是：全局最优解一定包含着子链的最优解。如果左边子链存在比 m[i][k] 更优的策略，那么全局方案也能替换成更优策略而不会影响右边，于是全局就不是最优了，矛盾。这个反证逻辑是动态规划正确性的标准证明框架，面试时讲清楚比单纯背代码有用得多。

3.3 为什么必须按区间长度从小到大填表

状态和转移方程都清楚了，接下来一个非常容易踩的坑就是：填表顺序。

m[i][j] 依赖 m[i][k] 和 m[k+1][j]。观察这两个子问题的区间长度：

• m[i][k] 的长度是 k - i + 1；
• m[k+1][j] 的长度是 j - k。

由于 k 在 i 和 j 之间，这两个长度都严格小于 j - i + 1。也就是说，一个区间的最优解只依赖更短区间的最优解，绝不依赖更长区间。这给了我们一个天然的填表策略：外层循环枚举区间长度 l，从 2 到 n，内层枚举所有长度为 l 的区间 [i, j]，再内层枚举分割点 k。

为什么不能换成"外层枚举 i、内层枚举 j"这种常见套路？因为当你计算 m[1][n] 时，你需要 m[2][n] 这个值。如果你按 i 从 1 到 n 的顺序填表，算到 i=1、j=n 的时候，m[2][n] 还没被算过，因为 i=2 这层还没轮到。这就是经典的"依赖了尚未计算的表项"。而按区间长度从小到大填，任何需要的子区间都比当前区间短，早已在之前的轮次中填好了。

这个填表顺序是区间 DP 类问题的通用法则。不只是矩阵连乘，石头合并、回文串划分、多边形剖分，只要状态是连续区间，一律按区间长度从短到长来遍历。把这个规律记在心里，能帮你省下大量调试时间。

4. 完整代码实现与下标暗坑

4.1 一份带注释的 Python 写法

先给一份最经典的 Python 实现，逻辑严谨，适合课程作业和复习：

def matrix_chain_order(p): n = len(p) - 1 # 矩阵个数 # m[i][j] 表示 Ai..Aj 的最小乘法次数，表大小 (n+1)x(n+1) m = [[0] * (n + 1) for _ in range(n + 1)] # s[i][j] 记录让 m[i][j] 取最小值的分割点 k s = [[0] * (n + 1) for _ in range(n + 1)] # l 是区间长度，从 2 开始，因为长度为 1 的区间代价已经是 0 for l in range(2, n + 1): for i in range(1, n - l + 2): j = i + l - 1 m[i][j] = float('inf') for k in range(i, j): cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j] if cost < m[i][j]: m[i][j] = cost s[i][j] = k return m, s

这段代码有个细节：range(1, n - l + 2)很多人第一次看不懂。它的作用是保证 j = i + l - 1 不超过 n。举个例子，n=5，l=3 时 i 最大是 3，j 最大是 5，i 的取值范围是 1 到 3。n-l+2 = 5-3+2 = 4，range(1,4) 正好是 1,2,3。可以这么记忆：区间右端点 j 必须 ≤ n，所以 i ≤ n - l + 1，循环里写成 range(1, n - l + 2) 是因为 range 右边是开区间。

调用方式：

p = [10, 20, 50, 1] m, s = matrix_chain_order(p) print(m[1][3]) # 1200

4.2 p 数组下标映射：p[i-1] × p[k] × p[j] 逐项拆解

我见过太多人在这一步翻车，所以要专门拆一下下标逻辑。

p 数组长度为 n+1，矩阵 Ai 的尺寸是 p[i-1] × p[i]。比如 p = [10, 20, 50, 1]：

• A1 是 p[0]×p[1]，即 10×20；
• A2 是 p[1]×p[2]，即 20×50；
• A3 是 p[2]×p[3]，即 50×1。

现在计算 m[i][j]，也就是 Ai 到 Aj 连乘。最后一部把左边和右边乘起来需要怎样的乘法次数？

左边 Ai 到 Ak 连乘的结果矩阵是 p[i-1] × p[k]，右边 Ak+1 到 Aj 连乘的结果矩阵是 p[k] × p[j]。因为矩阵维度是首尾相接的，中间的公共维度就是 p[k]。所以最后一步的乘法次数是：

p[i-1] × p[k] × p[j]

这里三个下标的规律其实很好记："左端点减一，分割点，右端点"。写代码时先把这三个变量打出来对一遍，再放进乘法里：

left_dim = p[i - 1] mid_dim = p[k] right_dim = p[j] cost = m[i][k] + m[k + 1][j] + left_dim * mid_dim * right_dim

把变量名写得清清楚楚，比一行写完整条表达式更能减少低级错误。实际开发中我也会建议别人这样写，虽然看起来啰嗦，但可读性和可维护性都更好。

4.3 C++ 还是 Python？课程实现的一点个人建议

如果是课程作业或者面试手写，我个人更推荐先用 Python 把逻辑跑通，因为数组初始化和循环边界写起来更省心。如果题目要求提供 C++ 版本，核心代码也很短：

#include <vector> #include <algorithm> using namespace std; const int INF = 1e9; vector<vector<int>> matrixChainOrder(const vector<int>& p) { int n = p.size() - 1; vector<vector<int>> m(n + 1, vector<int>(n + 1, 0)); vector<vector<int>> s(n + 1, vector<int>(n + 1, 0)); for (int l = 2; l <= n; l++) { for (int i = 1; i <= n - l + 1; i++) { int j = i + l - 1; m[i][j] = INF; for (int k = i; k < j; k++) { int cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k; } } } } return m; }

需要注意 C++ 中int可能溢出。当矩阵维度是几千级别、n 上百时，乘积会超过 2^31。正规做法是用long long装所有 DP 值。这一点在课程里不常考，但在真实工程或面试手写时会是个加分项。

5. 把最优方案找回来：s 表与递归输出加括号

5.1 分割点记录表到底在记录什么

只求出最小乘法次数还不够，很多时候问题会要求"请输出最优的加括号方案"。这时候就要用到 s 表。

s[i][j] 记录的就是：在使 m[i][j] 取得最小值的所有分割点 k 中，我们采用的是哪一个。换句话说，s[i][j] 告诉你，区间 [i, j] 的最优解法是在哪个位置断开的。

这个表的结构和 m 表一样。对角线不需要填，每个非对角线格子填一个介于 i 和 j-1 之间的整数。例如前面三矩阵例子 p = [10, 20, 50, 1]，算完之后：

• s[1][2] = 1，表示 A1·A2 的最优断点是 k=1；
• s[2][3] = 2，表示 A2·A3 的最优断点是 k=2；
• s[1][3] = 1，表示 A1·A2·A3 的整体最优断点是 k=1。

5.2 递归回溯：把一张表翻译成括号表达式

有了 s 表，输出最优括号就变成了一次递归遍历：

def print_parens(s, i, j): if i == j: return f"A{i}" k = s[i][j] left = print_parens(s, i, k) right = print_parens(s, k + 1, j) return f"({left}{right})"

按 s[1][3] = 1，先递归左边 [1,1]，输出 A1；再递归右边 [2,3]，而 s[2][3] = 2，右边继续递归得到 (A2A3)。拼接结果是 (A1(A2A3))。

这里有个容易误解的小地方：print_parens(s, i, k)里的 k 是上一层选好的分割点，而递归进入 [i, k] 之后，会自动读取 s[i][k] 作为新的分割点。所以整个过程不需要再传别的参数，一张 s 表足够。

如果你担心递归深度，n 一般不会超过几百，递归深度和矩阵个数同级，正常没问题。但如果 n 非常大或者环境限制递归深度，也可以用栈模拟递归的输出顺序，不过课程场景通常不需要。

5.3 怎么验证结果：手动填表对照法

我教过的不少学生在做完这个题之后，不知道自己的结果对不对。这里给一个非常实用的验证方法：拿一个四矩阵的例子，手动把 m 表填一遍。

假设有一个四矩阵链，p = [5, 4, 6, 2, 7]，也就是 A1:5×4，A2:4×6，A3:6×2，A4:2×7。

• 长度 2：
  • m[1][2] = 5×4×6 = 120
  • m[2][3] = 4×6×2 = 48
  • m[3][4] = 6×2×7 = 84
• 长度 3：
  • m[1][3] = min( m[1][1] + m[2][3] + 5×4×2, m[1][2] + m[3][3] + 5×6×2 )
  • k=1：0 + 48 + 40 = 88
  • k=2：120 + 0 + 60 = 180
  • 所以 m[1][3] = 88，s[1][3] = 1
  • 同理 m[2][4]：
    • k=2：0 + 84 + 4×6×7 = 252
    • k=3：48 + 0 + 4×2×7 = 104
    • 所以 m[2][4] = 104，s[2][4] = 3
• 长度 4：
  • m[1][4] = min(
    • k=1：0 + m[2][4] + 5×4×7 = 104 + 140 = 244
    • k=2：m[1][2] + m[3][4] + 5×6×7 = 120 + 84 + 210 = 414
    • k=3：m[1][3] + 0 + 5×2×7 = 88 + 70 = 158
  • )
  • 结果是 158，s[1][4] = 3。

做完这步，再用代码跑一遍，m[1][4] 应该等于 158，输出的括号方案是 ((A1(A2A3))A4) 或者等价形式。能对上就说明状态定义、转移方程和代码实现都正确。这个"手算对照"的习惯，到今天我做复杂算法题还在用。

6. 复杂度分析与常见坑位盘点

6.1 时间空间复杂度，以及是否可以优化

矩阵连乘问题的时间复杂度是 O(n³)，空间复杂度是 O(n²)。

这个复杂度是怎么来的？三重循环：外层枚举区间长度 l，最多 n 种；中层枚举区间起点 i，最多 n 种；内层枚举分割点 k，最多 n 种。乘法次数就是 O(n³)。空间上需要 m 表和 s 表，每张都是 n×n 的规模，所以 O(n²)。

O(n³) 在算法题里属于"中等偏重"的复杂度。n 到 100 很轻松，n 到 1000 就有点压力了，n 到 5000 基本不可行。所以这个基础版算法适合小规模精确求解。如果需要优化，通常不是优化 DP 本身，而是利用问题的特殊结构。

有一个经典的加速方向：如果维度序列满足某种单调性，转移的最优决策点 k 也具有单调性，可以用四边形不等式优化，把复杂度降到 O(n²)。不过这个优化需要性质分析且实现细节多，课程阶段很少有人深挖，知道有这条路就行。

6.2 我见过最容易翻车的三个位置

第一个翻车点，前面已经说过，就是外层循环顺序写错。把for l写成for i，结果 m[2][n] 还没算就拿来用，程序输出的都是诡异的大值。排查方法很简单：先做小规模手算对照，或者打印 m 表的填充顺序，看有没有使用未计算的格子。

第二个翻车点是初始化。很多人把 m[i][i] 初始化为某个大数，而不是 0。这样计算所有长度大于 1 的区间时，枚举到 k=i 或者 k=j-1 会带上一个错误的初始值。记住：单个矩阵不需要乘法，代价一定是 0，不用犹豫。

第三个翻车点是边界。比如循环是range(i, j)，分割点 k 的范围如果不小心写成了range(i, j+1)，就会访问 m[j+1][j] 或者越界。k 的最大值是 j-1，因为右边子链至少要有一个矩阵。写代码时把 k 的取值范围和"右边至少还有一个矩阵"这句话对应起来，就不容易错。

我统计过给学生改作业时的错误分布：大概一半是填表顺序错，三成是下标或者初值错，剩下的是输出方案时递归边界写错。这些坑都是"看似简单、一写就废"的典型。

6.3 变种问题：输出方案、统计最优方案数、断链表示

矩阵连乘还有一些常见的变体，课程和面试都可能出现。

第一个变种是要求输出所有最优方案。标准做法是在计算 m[i][j] 时，用一个小数组把所有取得最小值的 k 都记录下来，输出时再逐一递归。注意可能遇到指数级方案的情况，n 稍微大一点就很多，所以题目一般只要求"任意输出一种"或者"统计方案数"。

第二个变种是统计最优加括号方案的数量。思路不算复杂：用一个 dp_cnt 表，长度 1 时方案数为 1；计算长度大于 1 的区间时，求所有 k 中满足 cost == m[i][j] 的分割点，把左边方案数乘以右边方案数累加起来。注意这里不是简单的"总方案数"，而是"达到最小代价的方案数"，所以必须同时参照 m 表判断。

第三个变种是把加括号方案理解成一棵二叉树。每个区间 [i, j] 是一棵子树，分割点 k 是根。这棵树的中序遍历就是矩阵下标 1 到 n，而后缀遍历或前序遍历则对应某种"计算顺序"。理解这一点之后，矩阵连乘问题和"最优二叉搜索树""凸多边形最优三角剖分"这几个经典 DP 问题就串起来了，它们都是同一类区间划分问题的不同外壳。

7. 从教学题到工程问题：矩阵连乘的思想在哪些地方继续发光

7.1 矩阵链乘的"运算顺序"问题在真实场景里无处不在

矩阵连乘在算法课里是一道经典习题，但它绝不是纸上谈兵。只要你的程序里出现"多个矩阵连续相乘"，就存在选择最优运算顺序的问题。

我举一个很朴素的生产场景。某项目里需要计算 A × B × C × D，其中 A 是 200×300，B 是 300×500，C 是 500×10，D 是 10×800。如果按照从左到右的顺序算，最开始的中间矩阵就是 200×500，后面还有 200×10 等中间结果，整体计算量明显偏高。用矩阵连乘算法算一遍之后，发现优先算 B×C 能显著减少中间矩阵的规模，计算量能下降一个数量级。

类似的场景在数值计算库、图形学变换、深度学习模型推理中都存在。比如深度学习里连续做若干次矩阵乘，中间张量的形状各不相同，选择什么样的结合顺序，直接影响 FLOPs 和显存占用。虽然是神经网络的框架层在做这类优化，但背后的思想仍然是矩阵连乘问题的区间 DP 思路。

7.2 当 n 变大时：从精确转近似，但区间 DP 思想不变

前面说过 O(n³) 的限制。真实场景中如果矩阵链很长，精确求解会不可接受，这时就要退而求其次：用贪心、随机搜索、启发式算法去找一个"足够好"的加括号方案。比如可以每次贪心地选择当前乘法代价最小的两个相邻矩阵先乘，这种方法不能保证全局最优，但速度很快，而且大部分情况下结果相当可用。

工程上还有一个思路是"划分治之"：把大链切成长度相近的若干段，每段用精确 DP 求解，段与段之间再按一定顺序合并。这其实还是在做"先分段再整体"的区间思想。

但不管用什么启发式，区间 DP 的 m 表和 s 表仍然是分析这类问题最好的出发点。因为你至少要能评估一种加括号方案的成本，才能做优劣比较，而矩阵连乘 DP 教你的正是"给定区间求最小成本"的精确计算方法。从这个意义上说，课程里的 O(n³) 算法不是终点，是后续一切方案的基础设施。

7.3 向相关经典 DP 延伸：同一个骨架，不同的外壳

矩阵连乘问题掌握之后，有几个问题可以顺路一起学，因为它们本质是同一套区间 DP 框架：

• 凸多边形的最优三角剖分：状态同样是区间，转移同样是枚举分割点，只是代价函数从"矩阵乘法次数"换成了"三角形权值之和"。
• 石子合并问题：在一条线上合并相邻石子堆，每次合并的代价是两堆重量之和，求最小总代价。状态是区间 [i, j]，转移是枚举最后合并的分割点，几乎和矩阵连乘一模一样。
• 最优二叉搜索树：也是区间上的动态规划，但它的代价计算方式带上了访问概率，转移方程会稍微复杂一些，不过骨架逻辑相通。

把这几个题放在一起对比学习，比单独刷一个题效率高得多。你很快会发现，区间 DP 的核心三件事——区间状态、分割点枚举、按长度填充——在每一道题里都成立，区别只是代价函数的形态不同。

说回实践层面的体会。矩阵连乘是我在算法课程里刷过最多次的经典题之一，每次重新手写，都会对"状态设计"和"填表顺序"多一层理解。对初学动态规划的人，我强烈建议不要只盯着代码敲，一定亲手画一张 m 表，体会每个格子是怎么依赖其他格子的。动态规划不是一个"背模板去套"的知识点，而是"把重复计算变成查表"的思维方式。矩阵连乘问题，恰恰是最适合建立这种思维的第一块跳板。