大家如果还记得方格取数这道题的话就可以联想起这两者的区别 方格取数也是找两条路径，并且选取完一个点就将其价值置为0，而这道题目就是将价值转换为负无穷就是不能走
但其实这两者本质是一样的 所以可以用方格取数题目的代码，四维dp优化三维 枚举四个方向转移
至于这两者本质一样的证明（来源）：
代码：
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N=60;
int w[N][N],n,f[2*N][N][N],m,inf=-INT_MAX/2;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i ){
for(int j=1;j<=m;j )cin>>w[i][j];
}
for(int k=1;k<=n m;k ){
for(int i1=1;i1<=n;i1 ){
for(int i2=1;i2<=n;i2 ){
int j1=k-i1,j2=k-i2;
if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
int &x=f[k][i1][i2],t=w[i1][j1];
t =w[i2][j2];
x=max(x,f[k-1][i1-1][i2-1] t);
x=max(x,f[k-1][i1-1][i2] t);
x=max(x,f[k-1][i1][i2-1] t);
x=max(x,f[k-1][i1][i2] t);
}
}
}
}
cout<<f[n m][n][n]<<endl;
}
