baekjun 행렬의 곱셈순서

 D[i][j] = min(D[i][k] + D[k+1][j] + m[i][0] * m[i][1] * m[j][1])  if i <= k < j

#include <iostream>
#include <cstring>
using namespace std;
 
int matrix[501][2];
int cache[501][501];
 
// D[i][j] = min(D[i][k] + D[k +1][j] + m[i][0] * m[k][1] * m[j][1]);
 
int multrix(int y, int x){
    if(y == x) return 0;
    if(y + 1 == x) return matrix[y][0] * matrix[y][1] * matrix[x][1]; // 없어도 되지만 속도문
    if(cache[y][x] != -1) return cache[y][x];
    int &ret = cache[y][x];
    ret = -1;
    for(int k = y; k < x; k++){
        int tmp = multrix(y, k) + multrix(k + 1, x);
        tmp += matrix[y][0] * matrix[k][1] * matrix[x][1];
        if(ret == -1 || ret > tmp){
            ret = tmp;
        }
    }
    return ret;
}
 
int main(){
    int N;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    for(int i=1; i <= N; i++){
        cin >> matrix[i][0] >> matrix[i][1];
    }
    cout << multrix(1, N);
    return 0;
}