矩阵连乘

#include <bits/stdc++.h>
using namespace std;
int n;
int m[100][100],s[100][100];
int p[100];

int dp()
{
    memset(m,0,sizeof(m));//初始话数组
    memset(s,0,sizeof(s));//初始话数组
    for(int r=2;r<=n;++r)//矩阵连乘的规模（由2->n）
    {
        for(int i=1;i<=n-r+1;++i)//动态划分长度为r的连乘区间的起点
        {
            int j = i+r-1;//计算出矩阵的终点位置
            m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//初始区间i->j的最优解
            s[i][j] = i;//初始划分位置
            for(int k=i+1;k<j;++k)//寻找最优解（最优划分位置）
            {
                int t = m[i][k]+m[i][k+1]+p[i-1]*p[k]*p[j];//计算连乘的乘法次数
                if(t<m[i][j])//判断是否为最优解
                {
                    m[i][j]=t;//更新最小乘法次数
                    s[i][j]=k;//更新最优划分位置
                }
            }
        }
    }
    return m[1][n];
}
void print(int i,int j)//打印结果
{
    if(i==j)
    {
        printf("A[%d]",i);
        return ;
    }
    printf("(");
    print(i,s[i][j]);
    print(s[i][j]+1,j);
    printf(")");
}
int main()
{
    printf("输入矩阵个数:");
    cin >> n;
    printf("矩阵的高度以及最后结果的宽度\n");
    for (int i = 0; i <= n; ++i)
    {
        cin >> p[i];
    }
    printf("最小乘法次数：%d\n",dp());
    print(1, n);
    system("pause");
}