(프로그래머스 JS)최적의 행렬 곱셈

https://school.programmers.co.kr/learn/courses/30/lessons/12942

프로그래머스

 

 

백준 문제에도 동일한 유형이 있다.

아래 링크에 설명이 있으니 참고!

https://eunchanee.tistory.com/294

(백준 c++)11049 행렬 곱셈 순서

function solution(matrix_sizes) {
    const { length } = matrix_sizes;
    const dp = Array.from({length: length + 1}, () => Array(length + 1).fill(0));
    
    matrix_sizes = [[0, 0], ...matrix_sizes];
    
    for(let i = 1; i < length; i++){
        for(let x = 1; x + i <= length; x++){
            const y = x + i;
            
            dp[x][y] = Infinity;
            
            for(let j = x; j < y; j++){
                dp[x][y] = Math.min(dp[x][y], dp[x][j] + dp[j + 1][y] + matrix_sizes[x][0] * matrix_sizes[j][1] * matrix_sizes[y][1]);
            }
        }
    }
    
    return dp[1][length];
}