O($n^4$)

$f[i1][j1][i2][j2]$表示从左上角第一条路线走到$(i1,j1)$,第二条路线走到(i2,j2)的最大值,分别枚举不同的过来的情况。

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int f[N][N][N][N],w[N][N];
//f[i][j][i1][j1] 表示第一条路线到(i,j)和第二条路线到(i1,j1)的最大好心程度
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    memset(f,-0x3f,sizeof f); //初始化无穷大
    f[0][1][0][1]=0; //起点
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int i1=1;i1<=n;i1++)
            {
                for(int j1=1;j1<=m;j1++)
                {
                    int t1=w[i][j],t2=w[i1][j1]; //走到两个位置
                    if(i==i1&&j==j1) t1=0; //同一个点
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i-1][j][i1-1][j1]+t1+t2); //上上
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i][j-1][i1][j1-1]+t1+t2); //左左
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i][j-1][i1-1][j1]+t1+t2); //左上
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i-1][j][i1][j1-1]+t1+t2); //上左
                }
            }
        }
    }
    cout<<f[n][m][n][m]; //走到
    return 0;
}

O($n^3$)

$f[k][i][i2]$表示第一条路线走到$(i,k-i)$,第二条路线走到$(i1,k-i1)$的最大值,类似于从对对角线开始递推。

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int f[N+N][N][N],w[N][N];
//f[k][i][i1] 表示第一条路线走到(i,k-i)和第二条路线走到(i1,k-i1)的最大值 
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
        {
        	cin>>w[i][j];
		}
	}
    memset(f,-0x3f,sizeof f); //初始化步数 
    f[1][0][0]=0;//初始化起点 
    for(int k=2;k<=n+m;k++) //枚举步数 
    {
        for(int i=1;i<=n;i++) //第一个点的横坐标 
        {
            for(int i1=1;i1<=n;i1++) //第二个点的横坐标 
            {
                int j=k-i,j1=k-i1; //计算两个点的纵坐标 
                int t=w[i][j];
                if(i!=i1) t+=w[i1][j1]; //不是同一个点 
                if(j>=1&&j<=m&&j1>=1&&j1<=m) //纵坐标合理 
                {
                    f[k][i][i1]=max(f[k][i][i1],f[k-1][i-1][i1-1]+t);
                    f[k][i][i1]=max(f[k][i][i1],f[k-1][i][i1-1]+t);
                    f[k][i][i1]=max(f[k][i][i1],f[k-1][i-1][i1]+t);
                    f[k][i][i1]=max(f[k][i][i1],f[k-1][i][i1]+t);
                }
            }
		}
    }
    cout<<f[n+m][n][n]<<endl;
    return 0;
}

证明 首先， 从右下角回传可以等价为从左上角同时传两次。要想两个路径除了起点和终点之外没有交点，那么肯定有一条路径完全位于另一条的上方。 现在考虑路径有交点的情况：

这种情况其实转换起来很简单，只要把位于红色线段上方的蓝色线段交换颜色就可以了，也就是说当红色处于蓝色的下方的时候，将红色的路径换成从蓝色的那段走是等效的（因为两条路径加起来经过的节点完全没有变）。

就可以得到：

但是这个时候虽然满足了红色路径完全在蓝色的上方，但是却有交点。但是因为所有节点的权值都为非负数，那么可以证明这种情况永远不可能是最优解。比如以交点（2，2）为例，蓝色从（3，1）绕道或者红色从（1，3）处绕道一定不会比两条路径都从（2，2）处走差。

绕过交点之后，可以得到蓝色虚线的方案，该方案一定不会比之前的两个实线的方案更差。（当然该方案也不一定是最优的，还要确定应该由蓝色还是红色来走原来的交点的位置。

结论 不论是在 方格取数 中，还是在本题中，最优解永远不会由两段相交的路径组成。 那么代码中的相关位置的判断在事实上是起到了上述的确定是让蓝色还是红色走虚线的效果。