연속행렬곱셈

#include <iostream>
using namespace std;
#define MX 101

int n, d[MX], dp[MX][MX], P[MX][MX];

void order(int i, int j){
    if(i==j){
        cout << "M" << i;
    }
    else{
        int k = P[i][j];
        cout << "(";
        order(i, k);
        order(k+1, j);
        cout << ")";
    }

}

int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> n;
        for(int i=0; i<=n; i++){
            cin >> d[i];
        }

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

                int minValue = 2e9;

                for(int k = i; k <j; k++){
                    int cur = dp[i][k] + dp[k+1][j] + d[i-1] * d[k] * d[j];
                    if(minValue > cur){
                        P[i][j] = k;
                        minValue = cur;
                    }
                }
                dp[i][j] = minValue;
            }
        }
        order(1, n);
        cout << '\n';
        cout << dp[1][n] << '\n';
    }
    return 0;
}