Matrix Chain Multiplication
矩阵链由 dims 描述：矩阵 i 有 dims[i] 行和 dims[i+1] 列，因此每个矩阵都能与下一个矩阵相乘。将一个 p × q 矩阵乘以一个 q × r 矩阵，需要进行 p × q × r 次标量乘法，结果是一个 p × r 矩阵。无论怎样放置括号，最终乘积都相同，但计算成本并不相同。返回将整个矩阵链相乘所需的最少标量乘法次数。
函数
- dimsinteger-array
- 链上的尺寸：矩阵 i 的维度为 dims[i] × dims[i+1]
- 返回值integer
- 将整个矩阵链相乘所需的最少标量乘法次数
约束条件
2 ≤ dims.length ≤ 100，因此这条链包含 1 到 99 个矩阵。1 ≤ dims[i] ≤ 100- 答案最大为 98 × 106，远小于 32 位有符号整数的范围。
示例
- 输入
- dims = [4, 10, 3, 12]
- 输出
- 264
- 解释
- 先将前两个矩阵相乘，运算量为 4 × 10 × 3 = 120，得到一个 4 × 3 矩阵；再将它与 3 × 12 矩阵相乘，运算量增加 144：总计 264。另一种顺序的运算量为 360 + 480 = 840。
- 输入
- dims = [6, 2, 7, 3, 5]
- 输出
- 132
- 解释
- 将 2 × 7 的结果乘以 7 × 3（42），将 2 × 3 的结果乘以 3 × 5（30），然后将 6 × 2 的结果乘以 2 × 5 的结果（60）：总共是 132。
- 输入
- dims = [3, 7]
- 输出
- 0
- 解释
- 只有一个矩阵 3 × 7，因此不需要进行乘法，代价为 0。
进阶
你还能计算出有多少种不同的加括号方式可以达到最小成本吗？
提示
逐个打开提示，每个都会多透露一点。
忘掉第一次乘法，想想最后一次乘法。无论你选择什么顺序，最后一步都是将链中某个左侧部分的乘积与其余部分的乘积相乘。
两个边界
left和right之间的矩阵乘积始终是一个dims[left] × dims[right]矩阵。因此，如果最后一步在边界split处分割这段矩阵链，代价就是dims[left] × dims[split] × dims[right]，而两部分都是同一问题规模更小的实例。在
best[left][right]中存储边界left和right之间矩阵相乘的最低成本方案（单个矩阵的成本为 0）。它是在严格位于两者之间的每个split中取最小值，计算方式为best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]。先计算较窄的区间，再计算较宽的区间。
题解
顺序会改变成本：第一个示例中是 264，对比 840。看看最后一次乘法。它将链左侧部分和右侧部分的乘积组合起来，而每一部分都是在更短链上解决的相同问题。用一个表记录链上各段的结果，就能将每个问题只解决一次，时间复杂度为 O(n³)。
用普通递归尝试每一种拆分方式
结果正确，但无法在最大的测试中运行完毕
思路
将链的边界编号为从 0 到 m-1，其中 m = dims.length：边界 k 的大小为 dims[k]。边界 left 和 right 之间的矩阵，无论按什么顺序相乘，都会得到一个大小为 dims[left] × dims[right] 的矩阵。因此，如果最后一步在 split 处分割这段链，那么这一步的代价就是 dims[left] × dims[split] × dims[right]，与两个块内部的计算过程无关。每个块都应以尽可能低的代价构建，因此 cheapest(left, right) 是遍历每个 split 后，两个块的代价与最后一步的代价之和中的最小值。尝试每一种最后一步，就能保证结果正确。
它会反复求解相同的片段：n 个矩阵需要进行 3^(n-1) 次调用，20 个矩阵大约需要 1.2 × 10^9 次调用，而不同片段只有大约 m²/2 个。
算法
- 为边界
left和right之间的矩阵编写cheapest(left, right)。 - 如果
right - left < 2，则只有一个矩阵：返回 0。 - 对于严格位于它们之间的每个
split，将cheapest(left, split)、cheapest(split, right)和dims[left] × dims[split] × dims[right]相加。 - 返回最小的和。
- 答案是
cheapest(0, m-1)。
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)使用记忆表的递归
思路
一次调用只取决于 left 和 right。将结果保存在 memo[left][right] 中，每个单元格的初始值都是 -1，这个值不可能是真实开销，后续调用会读取该单元格，而不是再次递归。大约 m²/2 个配对中的每一对只会求解一次，且拆分次数少于 m：复杂度为 O(n³)，对于 99 个矩阵，需要检查 161,700 次拆分。递归深度不会超过链的长度，因此任何调用栈都能容纳 100 个边界。
算法
- 将
memo初始化为m行m列，并将每个单元格设为 -1。 - 在
cheapest(left, right)中，如果矩阵链长度为 1，则返回 0；如果单元格的值不为 -1，则返回保存的成本。 - 否则，按照普通递归的方式计算每个
split的成本，并取最小值。 - 返回前，将这个最小值写入
memo[left][right]。 - 答案是
cheapest(0, m-1)。
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)通过拉伸填满表格宽度
思路
每个单元格只依赖更短的区间，因此循环可以从窄到宽填充 best[left][right]。宽度为 1 时只有一个矩阵，结果保持为 0；到达更宽的区间时，每次拆分的两部分都已经计算完成。对于 dims = [6, 2, 7, 3, 5]：
- 宽度为 2：
best[0][2] = 84，best[1][3] = 42，best[2][4] = 105。 - 宽度为 3：
best[0][3]的值是 78（拆分点为 1：0 + 42 + 36），best[1][4]的值是 72（拆分点为 3：42 + 0 + 30）。 - 宽度为 4：拆分点 1、2 和 3 分别得到 0 + 72 + 60 = 132、84 + 105 + 210 = 399 和 78 + 0 + 90 = 168，因此
best[0][4] = 132。
最外层的拆分点是边界 1，意味着最后相乘的是 6 × 2 的矩阵，这和第二个示例相同。时间和内存开销与记忆化版本相同，而且不需要递归。
算法
- 令
m = dims.length，并分配一个元素全为零的m × m表best。 - 让
width从 2 循环到m-1。在循环中，让left从 0 开始递增，直到right = left + width仍在边界范围内。 - 对于这段区间，计算从
left+1到right-1的每个split对应的best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]，并将最小值存入best[left][right]。 - 答案在
best[0][m-1]中。
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
易错点和边界情况
- 先乘最便宜的一对。对于
[10, 10, 1, 9]，最后一对的乘积最小（90），但之后的步骤需要花费 900，总计 990。先乘第一对只需花费 190。 - 从错误的单元格读取答案。
dims的条目数比矩阵数量多 1，所以答案是best[0][m-1]，而不是best[0][m]。 - 在外层循环中让
left递增。这样，left行会读取后面一行中仍为 0 的best[split][right]。把宽度放在外层循环中，或者让left递减。 - 遗漏只有一个矩阵的情况。
[3, 7]必须返回 0，而在 R 中，循环2:(m-1)会变成2:1并倒序运行，因此要加上保护条件。
常见问题3
矩阵链乘法的时间复杂度是多少？
表中大约有 n²/2 个区间，每个区间最多尝试 n 种分割方式，因此动态规划的时间复杂度为 O(n³)，空间复杂度为 O(n²)。对于 n 个矩阵，不使用记忆化的普通递归会进行 3^(n-1) 次调用。
为什么矩阵乘法的顺序很重要？
矩阵乘法满足结合律，因此 (AB)C 和 A(BC) 得到的矩阵相同，但中间矩阵的大小不同。在第一个例子中，(AB)C 会生成一个 4 × 3 矩阵，代价为 264；而 A(BC) 会生成一个 10 × 12 矩阵，代价为 840。
如何找到最优的加括号方式？
将获胜的划分存储在 choice[left][right] 中，与 best[left][right] 放在一起。打印时，单个矩阵打印其名称；较长的片段则打印左括号、截至 choice[left][right] 的部分、其后的部分，以及右括号。这会增加 O(n²) 的内存开销。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def matrixChainOrder(dims):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
dims = [4, 10, 3, 12]
预期输出
264