区间动态规划例题：矩阵连乘的最小乘法次数问题 题目描述 给定一个数组 p ，其中 p[i-1] × p[i] 表示第 i 个矩阵的维度（矩阵 A_i 的维度为 p[i-1] × p[i] ）。矩阵连乘的乘法次数取决于计算顺序。例如，三个矩阵 A_1(10×100) 、 A_2(100×5) 、 A_3(5×50) ，按 (A_1A_2)A_3 计算需要 10×100×5 + 10×5×50 = 7500 次乘法，而按 A_1(A_2A_3) 需要 100×5×50 + 10×100×50 = 75000 次。要求找到一种括号化方案，使得总乘法次数最小。 解题思路 定义状态 设 dp[i][j] 表示计算矩阵链 A_i 到 A_j 的最小乘法次数（ i ≤ j ）。 状态转移 若 i = j ，只有一个矩阵，无需乘法， dp[i][j] = 0 。 若 i < j ，可枚举分割点 k （ i ≤ k < j ），将链拆为 (A_i...A_k) 和 (A_{k+1}...A_j) 。 左右两部分的最小乘法次数分别为 dp[i][k] 和 dp[k+1][j] 。 合并两部分的乘法次数为 p[i-1] × p[k] × p[j] （因为左部分矩阵维度为 p[i-1] × p[k] ，右部分为 p[k] × 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) \] 计算顺序 按区间长度 len 从小到大的顺序计算： 先计算所有长度为 1 的区间（ len=1 即 i=j ），然后长度为 2、3，直到 len=n 。 答案 dp[1][n] 即为整个矩阵链的最小乘法次数。 详细步骤（以 p = [10, 100, 5, 50] 为例） 矩阵链 ： A_1(10×100) 、 A_2(100×5) 、 A_3(5×50) ， n=3 ， p 下标从 0 开始。 初始化 ： dp[i][i] = 0 。 计算长度为 2 的区间 ： dp[1][2] ： k=1 ， dp[1][1] + dp[2][2] + p[0]*p[1]*p[2] = 0 + 0 + 10*100*5 = 5000 。 dp[2][3] ： k=2 ， dp[2][2] + dp[3][3] + p[1]*p[2]*p[3] = 0 + 0 + 100*5*50 = 25000 。 计算长度为 3 的区间 ： dp[1][3] ： k=1 ： dp[1][1] + dp[2][3] + p[0]*p[1]*p[3] = 0 + 25000 + 10*100*50 = 75000 。 k=2 ： dp[1][2] + dp[3][3] + p[0]*p[2]*p[3] = 5000 + 0 + 10*5*50 = 7500 。 取最小值 7500 。 答案 ： dp[1][3] = 7500 ，对应顺序 (A_1A_2)A_3 。 关键点 区间动态规划通过枚举分割点，将问题分解为更小的子区间。 需注意矩阵维度的对应关系：第 i 个矩阵的维度是 p[i-1] × p[i] 。 时间复杂度 O(n³)，空间复杂度 O(n²)。