BOJ. Matrix multiplication order (11049)

Problem: BOJ 11049 — Matrix Chain Multiplication · 한국어 · 日本語

Interval dynamic programming

Let dp[i][j] be the minimum number of scalar multiplications needed to multiply matrices i through j in order. One matrix needs no multiplication, so dp[i][i] = 0. For an interval containing more than one matrix, choose the final split after matrix k: first compute the left chain i..k, then the right chain k+1..j, and multiply the two resulting matrices.

If matrix i has dimensions r_i × c_i, the problem guarantees compatible neighbors: c_i = r_(i+1). Therefore the left result has dimensions r_i × c_(k), the right result has dimensions r_(k+1) × c_j, and compatibility makes their shared dimension c_k = r_(k+1). The final multiplication costs r_i * c_k * c_j. Thus:

dp[i][j] = min(dp[i][k] + dp[k+1][j] + r_i * c_k * c_j) for i <= k < j.

Evaluate intervals from shorter to longer so both subinterval costs are already known. The sentinel is Number.MAX_SAFE_INTEGER, rather than a smaller arbitrary constant that can be less than a valid answer. Under the problem’s bounds the actual costs are below this sentinel and integer arithmetic remains exact. The algorithm takes O(N^3) time and O(N^2) space. When N = 1, the initialized diagonal is the answer, 0.

const stream = require('fs').readFileSync(0, 'utf-8').trim().split(/\n/);
const n = Number(stream[0]);
const dimensions = stream.slice(1).map((line) => line.split(' ').map(Number));
const dp = Array.from({ length: n }, () =>
  new Array(n).fill(Number.MAX_SAFE_INTEGER),
);

for (let i = 0; i < n; i++) dp[i][i] = 0;

for (let length = 2; length <= n; length++) {
  for (let start = 0; start + length <= n; start++) {
    const end = start + length - 1;
    for (let split = start; split < end; split++) {
      const cost =
        dp[start][split] +
        dp[split + 1][end] +
        dimensions[start][0] * dimensions[split][1] * dimensions[end][1];
      dp[start][end] = Math.min(dp[start][end], cost);
    }
  }
}

console.log(dp[0][n - 1]);