Question

动态规划矩阵连乘问题

我学的超级烂，写了下面一个程序，想实现矩阵连乘的动态规划问题，引用的例题是：A1A2A3A4A5A6 这六个矩阵连乘。A1为30*35的矩阵，A2为35*15，A3为15*5，A4为5*10，A5为10*20 ，A6为20*25
我想用M[6][6]来记录最少数乘次数，用S[6][6]来记录最优断点位置。
这个程序肯定漏洞百出，哪位高手不要见笑，替小弟调试一下，并注明我哪里出错了，小弟不胜感激。谢谢。
#include<iostream>
using namespace std;

void matrixChain(int &p,int [][]m,int [][]s)
{
int n=p.length-1;
for(int i=1;i<=n;i++) m[i][i]=0;
for(int r=2;r<=n;r++)
for(int i=1;i<n-r+1;i++)
{
int j=i+r-1;
int m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
int s[i][j]=i;
for(int k=i+1;k<j;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;
}
}
}
}
void main()
{
int P[]={35,15,5,10,20};
int M[6][6];
int S[6][6];
matrixChain(int &P[],int M[6][6],int S[6][6]);
for(int i=1;i<7;i++)
for(int j=1;j<7;j++)
{
cout<<M[i][j]<<" "<<S[i][j]<<endl;
}
}

Answer 1

可怜，100分还没人理你，给我吧。
动态规划问题可以有tD/eD的形式，n^t为问题的大小，n^e为问题所依赖的子问题的大小
1D/1D型，最长上升子序列
2D/0D型，最长公共子序列
2D/1D型，多源最短路径
2D/2D型，双背包问题
当然可以有3D/1D或者更高的。

动态规划题目千变万化，主要是要学会思考方法，要能看到题目很快找出题目中的状态，找准状态后就基本没有难度了