代码:
#include<iostream>
using namespace std;
const int N=60;
int w[N][N];
int f[2*N][N][N];
int main(){
int m,n;
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>w[i][j];
}
}
for(int k=2;k<=m+n;k++){
for(int i=1;i<k;i++){
for(int j=1;j<k;j++){
int &x=f[k][i][j];
int temp=w[i][k-i];
if(i!=j){
temp+=w[j][k-j];
}
x=max(f[k-1][i-1][j-1],x);//右右
x=max(f[k-1][i][j],x);//下下
x=max(f[k-1][i-1][j],x);//右下
x=max(f[k-1][i][j-1],x);//下右
x+=temp;
}
}
}
cout<<f[m+n][m][m]<<endl;
return 0;
}
我的问题:
- 为什么不能第一次走过后将第一次走过的地方清零,第二次在开始走,两者的和为最大?
- 为什么要两条路径一起走才能取得最大值呢?
- 在此代码中k表示的含义?
- 在此代码的循环中i,j 的取值范围是什么?
- 此代码为什么能保证两条路径不想交?
解惑:
- 问题1,2对于如下案例:
例如7*7的矩阵
0 0 2 3 0 0 0
0 0 3 0 0 0 0
0 0 3 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 4 0 0
0 0 0 0 4 0 0
0 0 2 0 4 0 0
如果他分两次走最后取得的结果一定比两条路径一起走的结果小2 !!! - 问题3
k=ix+iy; k=jx+jy; - 问题4
如果取值是<m,需要下边使用if语句将i,j的范围限定在1~n中,防止数组越界 - 问题5
本代码是将两条路径走的每一步作为一个节点,保证每一个节点都取最大值,
当i==j时,即两个路径所在的节点所属的格子是相同的,这时就+一次w[i][k-i]
重点就在这里,为什么加一次就能避免两条路径到同一个格子呢?
一条路径A+w[i][k-i],另一条路径B+0,因为每一个格子上的值均>0,所以这种走的方式一定不是
最优的,如果其中一条路径绕道走,那么绕道走后的结果一定是比有交点的情况要好的或者相等
而我们使用的DP就是求max,所以这种方法一定能避免路径经过相同的点取得最优解!!!