Question

c++的动态规划 关于二维数组的问题

// Matrix.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "conio.h"
#include <iostream>
using namespace std;

void MatrixChain(int* p, int n, int** m,int** s)
{
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;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
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 Traceback(int i,int j,int** s)
{
if(i==j)return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;
}
int main()
{
int p[7]={5,4,7,8,3,6,9};
int n=6;
int** m;
m=new int*[7];
int** s;
s=new int*[7];
MatrixChain(p,n,m,s);
Traceback(1,6,s);

return 0;
}

调试时提醒“Matrix.exe 中的 0x004114f4 处未处理的异常: 0xC0000005: 写入位置 0xcdcdcdd1 时发生访问冲突” 请各位大虾帮帮忙呀~
直接用数组报错：error C2664: 'MatrixChain' : cannot convert parameter 3 from 'int [7][7]' to 'int **' i:\算法\实验二\matrix\matrix\matrix.cpp 40

改变数组大小也没用哦~

Answer 1

#include "stdafx.h"
#include "conio.h"
#include <iostream>
using namespace std;

void MatrixChain(int* p, int n, int m[7][7],int s[7][7])
{
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;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
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 Traceback(int i,int j,int s[7][7])
{
if(i==j)return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;
}
int main()
{
int p[7]={5,4,7,8,3,6,9};
int n=6;
int m[7][7];
int s[7][7];
MatrixChain(p,n,m,s);
Traceback(1,6,s);
getchar();
return 0;
}

你的**c指针不能用 new *c 指针可以new 所以出错 直接用数组就可以了
上面代码我编译过了 绝对可以通过啊。

Answer 2

应该属于数组越界.,m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];这句中M[i+1][j],
从主函数来看,P 0--6.而m+1最大可达到7,数组越界.