使用矩阵链乘法求解最优乘法代价时结果为无穷大的问题排查

嘿，我来帮你看看这段代码的问题所在～

你遇到的输出无穷大的问题，核心原因是循环中分割点k的范围设置错误，导致某些子问题根本没有被计算到，最终保留了初始的Number.MAX_VALUE值，进而传递到整个递归结果中。

具体错误分析 #

你的代码里循环条件写的是for (let k = i; k < j - 1; k++)，这会导致：

• 当处理两个相邻矩阵相乘的情况（比如i=3，j=4，对应矩阵A3和A4），j-1=3，循环条件k < 3但i=3，循环体完全不会执行。此时ans还是初始的Number.MAX_VALUE，直接返回这个无穷大值，后续上层递归调用叠加这个值后，最终结果就变成了无穷大。
• 对于更长的矩阵链，你也漏掉了部分分割点，无法遍历所有可能的相乘组合，导致无法找到最优解。

修复后的代码 #

把循环条件改成k < j，让k遍历从i到j-1的所有分割点：

const p = [1, 2, 3, 4, 3];
function mcm(m, i, j) {
  if (i >= j) return 0;
  let ans = Number.MAX_VALUE;
  // 修正k的范围，覆盖所有可能的分割点
  for (let k = i; k < j; k++) {
    const temp = mcm(m, i, k) + mcm(m, k + 1, j) + m[i - 1] * m[k] * m[j];
    if (ans > temp) {
      ans = temp;
    }
  }
  return ans;
}
console.log(mcm(p, 1, p.length - 1)); // 输出30（正确的最优乘法次数）

额外优化建议 #

你当前的递归版本会重复计算大量子问题，效率很低。可以加入记忆化缓存来避免重复计算，提升性能：

const p = [1, 2, 3, 4, 3];
// 初始化记忆化数组，存储已计算过的子问题结果
const memo = Array.from({ length: p.length }, () => Array(p.length).fill(-1));

function mcm(m, i, j) {
  if (i >= j) return 0;
  // 已计算过直接返回缓存值
  if (memo[i][j] !== -1) return memo[i][j];
  
  let ans = Number.MAX_VALUE;
  for (let k = i; k < j; k++) {
    const temp = mcm(m, i, k) + mcm(m, k + 1, j) + m[i - 1] * m[k] * m[j];
    ans = Math.min(ans, temp); // 用Math.min简化赋值逻辑
  }
  // 缓存当前子问题结果
  memo[i][j] = ans;
  return ans;
}

console.log(mcm(p, 1, p.length - 1)); // 输出30

内容的提问来源于stack exchange，提问作者Amanda