使用矩阵链乘法查找有效成本时结果为无穷大

Question

我想了解矩阵链乘法。特别是问题Given a sequence of matrices, find the most efficient way to multiply these matrices together.

我尝试了以下方法，但它为结果打印了一些无穷大的值。我做错了什么？

const p = [1, 2, 3, 4, 3];

function mcm(m, i, j) {
 if (i >= j) return 0;
 else {
    let ans = Number.MAX_VALUE;
    let temp;
    for (let k = i; k < j - 1; k++) {
       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));

Answer 1

错误出现在您的 for 循环的结束条件中：

for (let k = i; k < j - 1; k++) {

应该是：

for (let k = i; k < j; k++) {

原因是j包含在要检查的范围内，所以k应该包括j-1 .

您正在接近无穷大，因为在您的代码中有些情况下循环根本不执行迭代（当 j-i==1 时），然后函数将 return Number.MAX_VALUE，这解释你得到的输出。

使用矩阵链乘法查找有效成本时结果为无穷大

Giving infinite as result when using matrix chain multiplication to find the efficient cost

javascript

algorithm

recursion

dynamic-programming

multiplication