[动态规划] 矩阵链乘法问题

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

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

struct Matrix {
    int row;
    int column;
};

int matrixChainCost(Matrix *ms, int n) {
    for (int scale = 2; scale <= n; scale++) {
        for (int i = 0; i <= n - scale; i++) {
            int j = i + scale - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k+1][j] + (ms[i].row*ms[k].column*ms[j].column));
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    int n;
    std::cin >> n;  //n个矩阵组成的矩阵链
    Matrix *ms = new Matrix[n];
    for (int i = 0; i<n; i++) {
        std::cin >> ms[i].row;      //第i个矩阵的行数
        std::cin >> ms[i].column;   //第i个矩阵的列数
    }
    std::cout << matrixChainCost(ms, n);
    system("pause");
    return 0;
}