Порядок умножения матриц

1function matrixChainOrder(dims: number[]): number {
2  const n = dims.length - 1 // число матриц
3  // d[i][j] = минимальная стоимость Ai × ... × Aj
4  const d: number[][] = Array.from({ length: n + 1 }, () =>
5    new Array(n + 1).fill(0))
6 
7  for (let len = 2; len <= n; len++) {
8    for (let i = 1; i + len - 1 <= n; i++) {
9      const j = i + len - 1
10      d[i][j] = Infinity
11      for (let k = i; k < j; k++) {
12        // разрез k: (Ai..Ak)(Ak+1..Aj)
13        const cost = d[i][k]! + d[k + 1][j]! +
14          dims[i - 1]! * dims[k]! * dims[j]!
15        if (cost < d[i][j]!) d[i][j] = cost
16      }
17    }
18  }
19 
20  return d[1][n]!
21}
22// (A1×A2)×A3 = 1500+3000 = 4500; A1×(A2×A3) = 9000+2700 = 11700