矩阵链乘问题

矩阵链乘问题描述：

• 给出n个矩阵M1,M2,,Mn,
• M为i * i+1阶的矩阵，i=1,2,,n,
• 找出使得乘法次数最小的计算M,M,.M的乘法顺序，该顺序称为计算MM,M,的最优顺序。

动态规划

最优子结构：n个矩阵M最小乘法次数的顺序由 i个和（n-i）个 矩阵相乘的次数相加再加1而得到 重叠子问题：i 个和（n-i）个相乘的矩阵当中，有些是重复计算了的。

状态：二维数组，i,j M （i -j）矩阵相乘的最小次数

/**
 * 解决矩阵链乘问题的核心函数 (无需修改)
 * @param {number[]} p - 维度数组。
 * @returns {{dp: number[][], s: number[][]}} 包含最小成本表和分割点表的对象
 */
function matrixChainOrder(p) {
    const n = p.length - 1;
    const dp = Array(n + 1).fill(0).map(() => Array(n + 1).fill(0));
    const s = Array(n + 1).fill(0).map(() => Array(n + 1).fill(0));
  
    for (let L = 2; L <= n; L++) {
      for (let i = 1; i <= n - L + 1; i++) {
        const j = i + L - 1;
        dp[i][j] = Number.MAX_SAFE_INTEGER;
        for (let k = i; k < j; k++) {
          const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
          if (cost < dp[i][j]) {
            dp[i][j] = cost;
            s[i][j] = k;
          }
        }
      }
    }
    return { dp, s };
  }
  

reference