矩阵连乘

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如：

A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ;

最后的结果为：((A1(A2A3))((A4A5)A6)) 最小的乘次为15125。

矩阵连乘

解题思路：能用动态规划的一个性质就是最优子结构性质，也就是说计算A[i:j]的最优次序所包含的计算矩阵子琏A[i:k]和A[k+1:j]的次序也是最优的。动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算（即先从最小的开始计算）。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。我们可以根据下面这个公式来计算结果。其中p[i-1]表示的是第i个矩阵的行数,p[k]表示i:k矩阵合起来后最后得到的列数，p[j]是k+1:j合起来后得到的列数。这个部分的计算方法其实就是计算两个矩阵相乘时总共的乘次数。

http://www.tyvj.cn/p/1198

#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 105
using namespace std;
int p[maxn],m[maxn][maxn],n;
int main()
{
    scanf("%d",&n);
    int i,j,k,r;
    for(i=0;i<=n;i++)
        scanf("%d",p+i);
    memset(m,0,sizeof(m));
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=n-i+1;j++)
        {
            r=j+i-1;
            m[j][r]=m[j][j]+m[j+1][r]+p[j-1]*p[j]*p[r];
            for(k=j+1;k<r;k++)
            {
                m[j][r]=min(m[j][r],m[j][k]+m[k+1][r]+p[j-1]*p[k]*p[r]);
            }
        }
    }
    printf("%d\n",m[1][n]);

}