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;
}