最优矩阵链乘顺序问题（最小化乘法总次数）
字数 3026 2025-12-12 22:49:12

最优矩阵链乘顺序问题（最小化乘法总次数）

题目描述
给定一个矩阵序列 \(A_1, A_2, \dots, A_n\)，其中矩阵 \(A_i\) 的维度为 \(p_{i-1} \times p_i\)。计算这些矩阵的乘积 \(A_1 A_2 \cdots A_n\)。由于矩阵乘法满足结合律，不同的加括号方式（即计算顺序）会导致标量乘法次数的巨大差异。你的任务是确定一个完全括号化方案，使得计算该乘积所需的标量乘法总次数最小，并返回这个最小次数。

例如，给定矩阵序列维度数组 \(p = [10, 30, 5, 60]\)，表示三个矩阵：\(A_1: 10 \times 30\)，\(A_2: 30 \times 5\)，\(A_3: 5 \times 60\)。两种加括号方式：

  • 方式1：\((A_1 A_2) A_3\)，乘法次数 = \(10 \times 30 \times 5 + 10 \times 5 \times 60 = 1500 + 3000 = 4500\)。
  • 方式2：\(A_1 (A_2 A_3)\)，乘法次数 = \(30 \times 5 \times 60 + 10 \times 30 \times 60 = 9000 + 18000 = 27000\)。
    最小次数是4500。

输入：一个整数数组 \(p\)，长度为 \(n+1\)，其中 \(p[i-1] \times p[i]\) 是矩阵 \(A_i\) 的维度（\(1 \le i \le n\)）。
输出：一个整数，表示最小标量乘法总次数。

解题过程

这是一个经典的区间动态规划问题，其核心是最优子结构：计算 \(A_i \cdots A_j\) 的最小代价，取决于如何将其拆分为两个子区间 \(A_i \cdots A_k\) 和 \(A_{k+1} \cdots A_j\) 的乘积。

1. 定义状态

设 \(dp[i][j]\) 表示计算矩阵链 \(A_i A_{i+1} \cdots A_j\) 的最小标量乘法次数（其中 \(1 \le i \le j \le n\)）。
注意：矩阵 \(A_i\) 的维度是 \(p_{i-1} \times p_i\)。
目标：求 \(dp[1][n]\)。

2. 状态转移方程

考虑将 \(A_i \cdots A_j\) 在某个位置 \(k\)（\(i \le k < j\)）处拆分为两部分：

\[(A_i \cdots A_k) \times (A_{k+1} \cdots A_j) \]

  • 计算左半部分 \(A_i \cdots A_k\) 的最小代价为 \(dp[i][k]\)。
  • 计算右半部分 \(A_{k+1} \cdots A_j\) 的最小代价为 \(dp[k+1][j]\)。
  • 将左右两个结果矩阵相乘的代价：左矩阵维度为 \(p_{i-1} \times p_k\)，右矩阵维度为 \(p_k \times p_j\)，因此乘法次数 = \(p_{i-1} \times p_k \times p_j\)。

所以：

\[dp[i][j] = \min_{i \le k < j} \left( dp[i][k] + dp[k+1][j] + p_{i-1} \times p_k \times p_j \right) \]

边界条件：当 \(i = j\) 时，只有一个矩阵，无需乘法，所以 \(dp[i][i] = 0\)。

3. 计算顺序

由于 \(dp[i][j]\) 依赖于更小的区间长度，我们应按区间长度 \(len\) 从小到大计算：

  1. 初始化：对所有 \(i\)，\(dp[i][i] = 0\)。
  2. 对长度 \(len = 2\) 到 \(n\)（即子链包含的矩阵个数）：
    • 对每个起点 \(i = 1\) 到 \(n-len+1\)：
      • 终点 \(j = i + len - 1\)。
      • 初始化 \(dp[i][j] = +\infty\)。
      • 对每个分割点 \(k = i\) 到 \(j-1\)：
        • 计算候选值 = \(dp[i][k] + dp[k+1][j] + p_{i-1} \times p_k \times p_j\)。
        • 更新 \(dp[i][j] = \min(dp[i][j], 候选值)\)。

4. 举例说明

以 \(p = [10, 30, 5, 60]\) 为例（\(n = 3\) 个矩阵）：

  • 初始化：\(dp[1][1] = dp[2][2] = dp[3][3] = 0\)。
  • 长度 \(len = 2\)：
    • \(i=1, j=2\)：\(k\) 只能取 1。
      \(dp[1][2] = dp[1][1] + dp[2][2] + p_0 \times p_1 \times p_2 = 0 + 0 + 10 \times 30 \times 5 = 1500\)。
    • \(i=2, j=3\)：\(k\) 只能取 2。
      \(dp[2][3] = 0 + 0 + 30 \times 5 \times 60 = 9000\)。
  • 长度 \(len = 3\)：
    • \(i=1, j=3\)：
      • \(k=1\)：\(dp[1][1] + dp[2][3] + p_0 \times p_1 \times p_3 = 0 + 9000 + 10 \times 30 \times 60 = 9000 + 18000 = 27000\)。
      • \(k=2\)：\(dp[1][2] + dp[3][3] + p_0 \times p_2 \times p_3 = 1500 + 0 + 10 \times 5 \times 60 = 1500 + 3000 = 4500\)。
      • 取最小值，\(dp[1][3] = 4500\)。

最终结果：\(dp[1][3] = 4500\)。

5. 时间复杂度与空间复杂度

  • 时间复杂度：\(O(n^3)\)，因为三层循环：长度 \(O(n)\)、起点 \(O(n)\)、分割点 \(O(n)\)。
  • 空间复杂度：\(O(n^2)\)，存储 \(dp\) 表。

6. 扩展：输出最优括号化方案

若要输出具体加括号方式，可额外维护一个数组 \(s[i][j]\) 记录使 \(dp[i][j]\) 取最小值的分割点 \(k\)，然后递归构造括号表达式。

总结
矩阵链乘问题通过区间DP，将大区间的最优解由两个小区间的最优解组合得到，是区间DP的经典例题。关键点在于理解状态定义、转移方程和按长度递增的顺序计算。

最优矩阵链乘顺序问题（最小化乘法总次数） 题目描述 给定一个矩阵序列 \( A_ 1, A_ 2, \dots, A_ n \)，其中矩阵 \( A_ i \) 的维度为 \( p_ {i-1} \times p_ i \)。计算这些矩阵的乘积 \( A_ 1 A_ 2 \cdots A_ n \)。由于矩阵乘法满足结合律，不同的加括号方式（即计算顺序）会导致标量乘法次数的巨大差异。你的任务是确定一个完全括号化方案，使得计算该乘积所需的 标量乘法总次数最小 ，并返回这个最小次数。 例如，给定矩阵序列维度数组 \( p = [ 10, 30, 5, 60] \)，表示三个矩阵：\( A_ 1: 10 \times 30 \)，\( A_ 2: 30 \times 5 \)，\( A_ 3: 5 \times 60 \)。两种加括号方式： 方式1：\( (A_ 1 A_ 2) A_ 3 \)，乘法次数 = \( 10 \times 30 \times 5 + 10 \times 5 \times 60 = 1500 + 3000 = 4500 \)。 方式2：\( A_ 1 (A_ 2 A_ 3) \)，乘法次数 = \( 30 \times 5 \times 60 + 10 \times 30 \times 60 = 9000 + 18000 = 27000 \)。 最小次数是4500。 输入 ：一个整数数组 \( p \)，长度为 \( n+1 \)，其中 \( p[ i-1] \times p[ i] \) 是矩阵 \( A_ i \) 的维度（\( 1 \le i \le n \)）。 输出 ：一个整数，表示最小标量乘法总次数。 解题过程 这是一个经典的区间动态规划问题，其核心是 最优子结构 ：计算 \( A_ i \cdots A_ j \) 的最小代价，取决于如何将其拆分为两个子区间 \( A_ i \cdots A_ k \) 和 \( A_ {k+1} \cdots A_ j \) 的乘积。 1. 定义状态 设 \( dp[ i][ j] \) 表示计算矩阵链 \( A_ i A_ {i+1} \cdots A_ j \) 的最小标量乘法次数（其中 \( 1 \le i \le j \le n \)）。 注意：矩阵 \( A_ i \) 的维度是 \( p_ {i-1} \times p_ i \)。 目标：求 \( dp[ 1][ n ] \)。 2. 状态转移方程 考虑将 \( A_ i \cdots A_ j \) 在某个位置 \( k \)（\( i \le k < j \)）处拆分为两部分： \[ (A_ i \cdots A_ k) \times (A_ {k+1} \cdots A_ j) \] 计算左半部分 \( A_ i \cdots A_ k \) 的最小代价为 \( dp[ i][ k ] \)。 计算右半部分 \( A_ {k+1} \cdots A_ j \) 的最小代价为 \( dp[ k+1][ j ] \)。 将左右两个结果矩阵相乘的代价：左矩阵维度为 \( p_ {i-1} \times p_ k \)，右矩阵维度为 \( p_ k \times p_ j \)，因此乘法次数 = \( p_ {i-1} \times p_ k \times p_ j \)。 所以： \[ dp[ i][ j] = \min_ {i \le k < j} \left( dp[ i][ k] + dp[ k+1][ j] + p_ {i-1} \times p_ k \times p_ j \right) \] 边界条件 ：当 \( i = j \) 时，只有一个矩阵，无需乘法，所以 \( dp[ i][ i ] = 0 \)。 3. 计算顺序 由于 \( dp[ i][ j ] \) 依赖于更小的区间长度，我们应按区间长度 \( len \) 从小到大计算： 初始化：对所有 \( i \)，\( dp[ i][ i ] = 0 \)。 对长度 \( len = 2 \) 到 \( n \)（即子链包含的矩阵个数）： 对每个起点 \( i = 1 \) 到 \( n-len+1 \)： 终点 \( j = i + len - 1 \)。 初始化 \( dp[ i][ j ] = +\infty \)。 对每个分割点 \( k = i \) 到 \( j-1 \)： 计算候选值 = \( dp[ i][ k] + dp[ k+1][ j] + p_ {i-1} \times p_ k \times p_ j \)。 更新 \( dp[ i][ j] = \min(dp[ i][ j ], 候选值) \)。 4. 举例说明 以 \( p = [ 10, 30, 5, 60 ] \) 为例（\( n = 3 \) 个矩阵）： 初始化：\( dp[ 1][ 1] = dp[ 2][ 2] = dp[ 3][ 3 ] = 0 \)。 长度 \( len = 2 \)： \( i=1, j=2 \)：\( k \) 只能取 1。 \( dp[ 1][ 2] = dp[ 1][ 1] + dp[ 2][ 2] + p_ 0 \times p_ 1 \times p_ 2 = 0 + 0 + 10 \times 30 \times 5 = 1500 \)。 \( i=2, j=3 \)：\( k \) 只能取 2。 \( dp[ 2][ 3 ] = 0 + 0 + 30 \times 5 \times 60 = 9000 \)。 长度 \( len = 3 \)： \( i=1, j=3 \)： \( k=1 \)：\( dp[ 1][ 1] + dp[ 2][ 3] + p_ 0 \times p_ 1 \times p_ 3 = 0 + 9000 + 10 \times 30 \times 60 = 9000 + 18000 = 27000 \)。 \( k=2 \)：\( dp[ 1][ 2] + dp[ 3][ 3] + p_ 0 \times p_ 2 \times p_ 3 = 1500 + 0 + 10 \times 5 \times 60 = 1500 + 3000 = 4500 \)。 取最小值，\( dp[ 1][ 3 ] = 4500 \)。 最终结果：\( dp[ 1][ 3 ] = 4500 \)。 5. 时间复杂度与空间复杂度 时间复杂度：\( O(n^3) \)，因为三层循环：长度 \( O(n) \)、起点 \( O(n) \)、分割点 \( O(n) \)。 空间复杂度：\( O(n^2) \)，存储 \( dp \) 表。 6. 扩展：输出最优括号化方案 若要输出具体加括号方式，可额外维护一个数组 \( s[ i][ j] \) 记录使 \( dp[ i][ j ] \) 取最小值的分割点 \( k \)，然后递归构造括号表达式。 总结 矩阵链乘问题通过区间DP，将大区间的最优解由两个小区间的最优解组合得到，是区间DP的经典例题。关键点在于理解状态定义、转移方程和按长度递增的顺序计算。