为什么我的这个dynamic解法有错误# JobHunting - 待字闺中
I*g
1 楼
高手看看，错在哪里了？
题目是找到从[0][0] 到[M][N]点的所有途径数 （如果a[i][j] ==0 就不能通过）
int numberOfPaths(int a[][1001],int M, int N) {
if (M <= 0 || N <=0) return -1;
int help[M][N];
if (a[M-1][N-1] == 0) {help[M-1][N-1] = 0;}
else {help[M-1][N-1] =1;}
for (int x = M-2 ; x >= 0; --x){
if (a[x][N-1] ==0 || help[x+1][N-1] ==0) help[x][N-1] = 0;
else help[x][N-1] = 1;
}
for (int y = N-2 ; y >=0; --y){
if (a[M-1][y] == 0 || help[M-1][y+1] ==0) help[M-1][y] = 0;
else help[M-1][y] =1;
}
for(int i=M-2;i>=0; --i)
{
for(int j=N-2;j>=0; --j){
if (a[i][j] ==0) help[i][j] =0;
else{
help[i][j] = help[i+1][j] + help[i][j+1];
}
}
}
return help[0][0];
}
int main(){
int M,N,i = 0,j = 0;
scanf("%d %d",&M,&N);
int a[1001][1001] = {};
for( i = 0;i < M;i++ )
for( j = 0;j < N;j++ )
scanf("%d",&a[i][j]);
printf("%dn",numberOfPaths(a,M,N));
return 0;
}
题目是找到从[0][0] 到[M][N]点的所有途径数 （如果a[i][j] ==0 就不能通过）
int numberOfPaths(int a[][1001],int M, int N) {
if (M <= 0 || N <=0) return -1;
int help[M][N];
if (a[M-1][N-1] == 0) {help[M-1][N-1] = 0;}
else {help[M-1][N-1] =1;}
for (int x = M-2 ; x >= 0; --x){
if (a[x][N-1] ==0 || help[x+1][N-1] ==0) help[x][N-1] = 0;
else help[x][N-1] = 1;
}
for (int y = N-2 ; y >=0; --y){
if (a[M-1][y] == 0 || help[M-1][y+1] ==0) help[M-1][y] = 0;
else help[M-1][y] =1;
}
for(int i=M-2;i>=0; --i)
{
for(int j=N-2;j>=0; --j){
if (a[i][j] ==0) help[i][j] =0;
else{
help[i][j] = help[i+1][j] + help[i][j+1];
}
}
}
return help[0][0];
}
int main(){
int M,N,i = 0,j = 0;
scanf("%d %d",&M,&N);
int a[1001][1001] = {};
for( i = 0;i < M;i++ )
for( j = 0;j < N;j++ )
scanf("%d",&a[i][j]);
printf("%dn",numberOfPaths(a,M,N));
return 0;
}
