[Link] https://www.acmicpc.net/problem/11049
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const stream = require('fs').readFileSync(0, 'utf-8').trim().split(/\n/);
const n = +stream[0],
max = 987654321,
arr = [];
const dp = Array.from(Array(n), () => new Array(n).fill(max));
for (let i = 0; i < n; i++) {
arr[i] = stream[i + 1].split(' ').map((e) => +e);
dp[i][i] = 0;
}
for (let diff = 1; diff < n; diff++)
for (let i = 0; i < n - diff; i++)
for (let j = i; j < i + diff; j++)
dp[i][i + diff] = Math.min(
dp[i][i + diff],
dp[i][j] +
dp[j + 1][i + diff] +
arr[i][0] * arr[j][1] * arr[i + diff][1],
);
console.log(dp[0][n - 1]);