[프로그래머스] 최적의 행렬 곱셈

😀요점

1. dp 사용해서 이전 계산 기록을 활용해야함 (효율성)
2. 전현서님의 DP를 사용한 문제 해설. 참고

😎풀이

function solution(matrix_sizes) {
    const n = matrix_sizes.length;
    let dp = Array(n).fill(0).map(() => Array(n).fill(0));

    for(let i = 1; i < n; i++) {
        for(let j = 0; j < n - i; j++) {
            let a = j;
            let b = j + i;
            dp[a][b] = Number.MAX_SAFE_INTEGER;

            for(let k = a; k < b; k++) {
                dp[a][b] = Math.min(dp[a][b], dp[a][k] + dp[k+1][b] + matrix_sizes[a][0] * matrix_sizes[k][1] * matrix_sizes[b][1]);
            }
        }
    }
    
    return dp[0][n-1];
}