[알고리즘] DP - 최소 행렬 곱셈

• N개의 행렬의 시퀀스가 있다. M1 x M2 x ... * MN
• 행렬의 Size를 나타내는 배열 d[] 가 있다.
  이 때 행렬 Mi의 Size는 d[i-1] x d[i] 이다.

행렬이 세 개 있다고 하자.
A, B, C 행렬 시퀀스가 있고 각각 크기는 (5x1), (1x7), (7x8) 이다.

이 때 A와 B를 먼저 곱할 경우 그 비용은 (5x1x7) + (5x7x8) = 315 이다.
그런데 B와 C를 먼저 곱할 경우 그 비용은 (1x7x8) + (5x1x8) = 96 이다.

즉 같은 행렬 시퀀스에서도 어떤 걸 먼저 곱하느냐에 따라 비용이 달라진다.
Dynamic Programming을 통해 어떤 순서로 곱해야 가장 적은 비용이 드는지 알아낼 수 있다.

마지막 곱하기에 집중하는 것이 핵심이다.
Mi부터 Mk까지의 최소 비용 + (마지막 곱하는 비용) + Mk+1부터 Mj까지의 최소 비용
= Di,j + (di x dk x dj) + Dk+1,j

모든 가능한 i,j에 대하여 모든 Di,j를 계산하면 약 n^2개의 경우의 수가 있다.

Pseudo Code

int M(int d[], int n)
{
	int D[n+1][n+1];
    for(int i=1; i<=n; i++)
    	D[i][i] = 0;
    for(int s=1; s<=n-1; s++) 
    {
    	minval = INF;
        for(int k=i; k<=i+s-1; k++)
        {
        	minval = min(minval, D[i][k]+D[k+1][i+s]+d[i-1]*d[k]*d[i+s]);         
        }
        D[i][i+s] = minval;
    }
    return D[1][n];
}         

이건 왜 DP인가?

• D[i][j] = min(D[i][k]+D[k+1][j]+d[i-1]*d[k]*d[j]) 라는 점화식이 변하지 않는다.
• Bottom up 방식으로 배열의 값을 활용한다.
  D[i][i] = 0 (i행렬에서 i행렬까지의 곱셈 비용이므로 곱할 횟수가 없음)
  D[1][4] = D[1][1]+D[2][4]+d[0]d[1]d[4]
  >> D[2][4] = D[2][3]+D[4][4]+d[1]d[2]d[4]
  >> >> D[2][3] = D[2][2]+D[3][3]+d[1]d[2]d[3]
  위와 같이 D[1][4]를 구할 때 D[2][4]가 필요, D[2][4]를 구할 때 D[2][3]이 필요
  

이해하려고 n번째 보는 중인데 어지럽다,,