백준 11049번 : 행렬 곱셈 순서 - dp

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

#include <iostream>
#include <climits>

using namespace std;

int N;
int d[503];
int matrix[503][2];
long long dp[503][503];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> matrix[i][0] >> matrix[i][1];
        d[i] = matrix[i][1];
    }

    d[0] = matrix[1][0];
    for (int diagonal = 1; diagonal <= N - 1; diagonal++) {
        for (int i = 1; i <= N - diagonal; i++) {
            int j = i + diagonal;
            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[j] * d[k]);
            }
        }
    }

    cout << dp[1][N] << '\n';
    return 0;
}