矩阵连乘问题 题目描述 给定一个数组 p[] ，其中 p[i-1] 和 p[i] 分别表示第 i 个矩阵的行数和列数（数组长度为 n+1，表示有 n 个矩阵）。要求找出一种矩阵连乘的顺序，使得计算矩阵连乘积所需的总标量乘法次数最少，并返回这个最少的乘法次数。 例如，对于 p = [10, 20, 30, 40] ，表示有三个矩阵：A₁(10×20)、A₂(20×30)、A₃(30×40)。不同的计算顺序会导致不同的乘法次数： (A₁A₂)A₃：10×20×30 + 10×30×40 = 6000 + 12000 = 18000 A₁(A₂A₃)：20×30×40 + 10×20×40 = 24000 + 8000 = 32000 最少乘法次数为 18000。 解题过程 1. 问题分析 矩阵乘法满足结合律，但不同计算顺序的代价差异巨大。若暴力枚举所有括号化方案，时间复杂度为卡特兰数级别，不可接受。动态规划通过保存子问题解避免重复计算。 2. 定义状态 设 dp[i][j] 表示计算从第 i 个矩阵到第 j 个矩阵（A_ i 到 A_ j）连乘所需的最少乘法次数。 目标：求 dp[1][n] （矩阵编号从 1 到 n）。 基础情况：当 i = j 时，单个矩阵无需乘法， dp[i][i] = 0 。 3. 状态转移方程 对于 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[ k]，列数 p[ j]）相乘的标量乘法次数 = p[i-1] * p[k] * p[j] 总代价： dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j] 需遍历所有可能的 k，取最小值： dp[i][j] = min{ dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j] } （对 k = i, i+1, ..., j-1） 4. 计算顺序 由于 dp[i][j] 依赖于更短的子链（即区间长度 len = j-i+1 更小的情况），应按区间长度从小到大计算： 外层循环：长度 len 从 2 到 n（len=1 时 dp[i][i]=0 ） 内层循环：起始下标 i 从 1 到 n-len+1，则 j = i+len-1 内层嵌套：遍历分割点 k 从 i 到 j-1 5. 示例计算 以 p = [10, 20, 30, 40] （n=3）为例： 初始化： dp[1][1]=0, dp[2][2]=0, dp[3][3]=0 len=2（两个矩阵）： dp[1][2] = p[0]*p[1]*p[2] = 10*20*30 = 6000 dp[2][3] = p[1]*p[2]*p[3] = 20*30*40 = 24000 len=3（三个矩阵）： i=1, j=3： k=1： dp[1][1] + dp[2][3] + 10*20*40 = 0 + 24000 + 8000 = 32000 k=2： dp[1][2] + dp[3][3] + 10*30*40 = 6000 + 0 + 12000 = 18000 取最小值 dp[1][3] = 18000 6. 复杂度分析 时间复杂度：O(n³)，三层循环（len、i、k） 空间复杂度：O(n²)，存储 dp 表 7. 关键点 正确理解矩阵维度 p[ i] 的含义：p[ i-1] 是 A_ i 的行数，p[ i] 是 A_ i 的列数。 按区间长度递增计算，确保子问题已求解。 实际问题中可额外记录分割点 k 以重构最优括号化方案。