[백준] #11049 행렬 곱셈 순서

문제

이것도 어떻게 풀어야할지 잘모르겠어서 다른 블로그를 참고했다.
점화식을 그래도 나타내면 되는 문제였다.
점화식: d(L,R)=d(L,k)+d(k+1,R)+C(k,k+1)
d(L,R): L번째 행렬부터 R번째 행렬까지 곱하는데 필요한 곱셈 연산 횟수의 최솟값
C(i,j): i번째 행렬과 j번째 행렬을 곱하는데 필요한 곱셈 연산 횟수

#include<iostream>
#include<algorithm>
#include<climits>


using namespace std;

typedef struct{
    int height, width;
}mat;

 mat arr[500];
 int dp[500][500];


int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i].height >> arr[i].width;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j + i < n; j++) {
            dp[j][j + i] = INT_MAX;;
            for (int k = 0; k <= i - 1; k++) {
                dp[j][j + i] = min(dp[j][j + k] + dp[j + k + 1][j + i]+ arr[j].height * arr[j + k].width * arr[j + i].width, dp[j][j + i]);
            }
        }
    }
    cout << dp[0][n - 1];
    return 0;
}