MatrixChain

#include<iostream>
using namespace std;
const int num = 4; //矩阵个数
//输入矩阵链的向量
int p[num+1]={10, 30, 20, 10, 200};
//int p[num+1]={30, 35, 15, 5, 10, 20};
//初始化
int m[num+1][num+1] = {0}, s[num+1][num+1] = {0};
int main(){
    //r表示步长
    for(int r = 2; r <= num; r++){
        //i表示起始位置
        for(int i = 1; i <= num - r + 1; i++){
            int j = i + r - 1; //计算终点位置
            m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
            s[i][j] = i;
            // 枚举从i到j中间每一个可能的划分位置
            for(int k = i + 1; k <= j - 1; k++){
                int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if ( t < m[i][j] ) {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
    cout<<m[1][num];
    return 0;
}