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

문제 설명

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

문제 풀이

• 다이나믹 프로그래밍으로 풀이하였다.
• 한가지 알아야할 사전지식은 행렬곱셈에서 결합법칙은 성립하지만 교환법칙은 성립하지 않는다는 것이다. (행렬의 순서는 바꿀 수 없음)
• 점화식은 다음과 같다.

  • DP[S][E] =S부터 E 인덱스까지 행렬곱에서 곱셈의 최솟값.
  • DP[S][E] = (S, E)를 두구간으로 나눈 모든 경우의 수를 고려하여 최소값 결정
  • DP[S][E] = MIN {
    - DP[S][S] + DP[S+1][E] + (두 결과 행렬을 곱할때 나오는 곱셈의 횟수)
    - DP[S][S+1] + DP[S+2][E] + ( ... )
    - ...
    - DP[S][E-1] + DP[E][E] + ( ... )
    }

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, INF = 987654321;
    public int[][] matrixs;
    public int[][] dp;

    //s인덱스부터 e인덱스까지 행렬을 곱했을 때 최소 횟수 리턴
    public int solve(int s, int e) {
        if (s == e) return 0;
        if (dp[s][e] != -1) return dp[s][e];

        int result = INF;
        //모든 구간 나눠보기
        for (int i = 0; i < e - s; i++) {
            int mid = s + i;
            int tmp = 0;
            tmp += solve(s, mid);
            tmp += solve(mid + 1, e);
            tmp += matrixs[s][0] * matrixs[mid][1] * matrixs[e][1];
            result = Math.min(result, tmp);
        }
        return dp[s][e] = result;
    }

    public int solution(int[][] matrix_sizes) {
        //초기화
        N = matrix_sizes.length;
        matrixs = matrix_sizes;
        dp = new int[N][N];
        for (int i = 0; i < N; i++) 
            Arrays.fill(dp[i], -1);

        //다이나믹 프로그래밍
        return solve(0, N-1);
    }
}