연쇄 행렬 곱셈 (Matrix chain multiplication)

행렬곱은 어떤 방향으로 결합하느냐에 따라 필요한 곱셈 횟수가 달라진다. 예를 들어, 크기가 각각 A = 2 x 5, B = 5 x 3, C = 3 x 4인 행렬이 있는 경우 A의 행과 열을 d₀, d₁, B의 행과 열을 d₁, d₂, C의 행과 열을 d₂, d₃으로 정의한다면 A(BC)와 (AB)C의 곱 연산 횟수는 아래와 같으며 곱 연산의 최소 횟수는 54이다.

A(BC) = d₀d₁d₃ + d₁d₂d₃ = 40 + 60 = 100

(AB)C = d₀d₁d₂ + d₀d₂d₃ = 30 + 24 = 54

동적 계획법을 이용하면 행렬의 개수가 n일때 수행될 곱 연산의 최소 횟수를 시간복잡도 O(n³)이내에 구할 수 있다. 점화식은 아래와 같다. dp[i][j]는 행렬 i에서 j까지 곱 연산의 최수 횟수이며, 만약 i = j일 경우 0으로 처리한다. 위의 A, B, C 행렬곱의 최소 연산 횟수가 계산되는 과정을 점화식과 함께 나타냈다.

dp[i][j] = min_i≤k≤j-1(dp[i][k] + dp[k+1][j] + d_id_kd_j-1)

dp[1][2] = min_1≤k≤1(dp[1][1] + dp[2][2] + d₀d₁d₂) = 0 + 0 + 30 = 30

dp[2][3] = min_2≤k≤2(dp[2][2] + dp[3][3] + d₁d₂d₃) = 0 + 0 + 60 = 60

dp[1][3] = min_1≤k≤2(dp[1][k] + dp[k+1][3] + d₀d_kd₃) = min(dp[1][1] + dp[2][3] + d₀d₁d₃, dp[1][2] + dp[3][3] + d₀d₂d₃)

아래는 동적 계획법으로 최소 곱 연산 횟수를 구하는 소스코드이다. 행렬의 최대 개수를 500개로 설정하였다.

#include <bits/stdc++.h>

 

using namespace std;

 

int main(void)

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin >> n;

    int d[501];

    for(int i = 0; i < n; i++) {

        cin >> d[i] >> d[i + 1];

    }

    int dp[501][501] = { 0 };

    for(int len = 2; len <= n; len++) {

        for(int i = 1; i <= n - len + 1; i++) {

            int j = i + len - 1;

            dp[i][j] = INT_MAX;

            for(int k = i; k <= j - 1; k++) {

                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (d[i - 1] * d[k] * d[j]));

            }

        }

    }

    cout << dp[1][n] << endl;

    return 0;

}