在计算机科学与数学中，动态规划是一种高效解决问题的技术，尤其适用于具有重叠子问题和最优子结构性质的问题。矩阵链乘法优化是动态规划的一个经典应用案例。该问题描述了如何通过最小化代价来确定一系列矩阵的最优计算顺序。
给定一组矩阵 $A_1, A_2, \ldots, A_n$，其中每个矩阵 $A_i$ 的维度为 $d_{i-1} \times d_i$。我们的目标是找到一种最经济的方式将这些矩阵按某种顺序相乘，即计算表达式 $(\ldots ((A_1A_2)A_3)\ldots A_n)$。
矩阵链乘法的代价主要由每次乘法操作中元素的数量决定。具体来说，如果两个维度分别为 $p \times q$ 和 $q \times r$ 的矩阵相乘，则需要进行 $pqr$ 次标量乘法运算来完成这次乘法。
动态规划的核心思想在于将原问题分解为子问题，并通过子问题的最优解来构建原问题的最优解。对于矩阵链乘法，我们可以通过构造一个二维数组 m 来记录每个子问题的最优代价。其中，m[i][j] 表示计算从 $A_i$ 到 $A_j$ 的所有子表达式的最小代价。
状态表示：我们使用一个二维数组 m 来存储矩阵链乘法的不同子问题的最优解。其中，m[i][j] 表示计算从第 i 个矩阵到第 j 个矩阵的所有子表达式的最小代价。
初始状态：对于单个矩阵的情况，即 $i = j$ 的情况，任何单独的矩阵乘法不需要进行任何标量乘法操作。因此，m[i][i] = 0。
通过动态规划的思想，我们可以通过以下递推公式来计算 m[i][j]：
[ m[i][j] = \min_{i \leq k < j} (m[i][k] + m[k+1][j] + p_{i-1} \cdot p_k \cdot p_j) ]
其中，$p_i$ 代表矩阵链中第 $i$ 个矩阵的维度之一（例如 d_{i-1} 或 d_i）。
初始化：根据矩阵链的长度初始化二维数组 m。
填表过程：使用嵌套循环从下至上、从小至大地填充 m 数组。外层循环定义了子问题区间 [i, j] 的大小，内层循环则遍历可能的分割点 k。
经过上述步骤后，我们可以得到矩阵链乘法的最小代价，即 m[1][n]。此外，我们还可以通过回溯数组来记录具体的计算顺序。
def matrix_chain_order(p):
n = len(p) - 1 # 矩阵数量为 p 的长度减一
m = [[0 for _ in range(n)] for _ in range(n)]
s = [[0 for _ in range(n)] for _ in range(n)]
# 初始化单个矩阵情况
for i in range(1, n + 1):
m[i-1][i-1] = 0
# 矩阵链的长度从2增加到n
for L in range(2, n+1):
for i in range(n-L+1):
j = i + L - 1
if i < j:
m[i][j] = float('inf')
for k in range(i, j):
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
if q < m[i][j]:
m[i][j] = q
s[i][j] = k
return m[0][n-1], s # 返回最小代价和最优分割点矩阵
# 示例输入
p = [30, 35, 15, 5, 10, 20, 25]
min_cost, s = matrix_chain_order(p)
print(f"最小成本：{min_cost}")
通过上述实现，我们可以计算出给定矩阵链乘法的最优计算顺序，并且能够找到最小化总运算量的方法。这种方法的时间复杂度为 $O(n^3)$，空间复杂度也为 $O(n^2)$。
这个例子展示了动态规划如何有效地解决复杂问题，并提供了一种系统化的方法来寻找全局最优化解。