等价于两人同时走，并且走相同步数。条件：i+j == x+y f[i,j,x,y]表示两人从 (1,1) 同步走到 (i,j)、(x,y) 的路径和的最大值 【参考程序】

#include<bits/stdc++.h>
using namespace std;
int f[31][31][31][31];//走一次就是f[31][31]，两次就加两维，变成两次同时走 
int a[31][31];
int mymax(int x1,int x2,int x3,int x4)
{
    return max(max(x1,x2),max(x3,x4));
}
int main()
{
    int n;scanf("%d",&n);
    int x,y,c;
    memset(a,0,sizeof(a));
    while(scanf("%d%d%d",&x,&y,&c)!=EOF)
    {
        if(x==0&&y==0&&c==0) break;a[x][y]=c;
    }
    memset(f,0,sizeof(f));
    for(int x1=1;x1<=n;x1++)
        for(int y1=1;y1<=n;y1++)
            for(int x2=1;x2<=n;x2++)
                for(int y2=1;y2<=n;y2++)
                {
                    //到达一个点(x,y)，f[x][y]只有f[x-1][y]或f[x][y-1]两种情况。 
            		//到达两个点(x1,y1)、(x2,y2)，f[x1][y1][x2][y2]有四种情况。
					int t;
                    if(x1==x2&&y1==y2) t=a[x1][y1];//如果(x1,y1)、(x2,y2)是一个地方，走完第一次的话，第二次时这个地方的价值就为0 
                    else               t=a[x1][y1]+a[x2][y2];
                    f[x1][y1][x2][y2]=mymax(f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1])+t;
                }
    printf("%d\n",f[n][n][n][n]);
    return 0;
}

利用约束条件，降维优化，令 i+j=x+y=k 表示走的步数 f[k,i,x]表示共走了k步，两人分别走到i行x行，取数的最大值

// 线性DP O(n^3)
#include<bits/stdc++.h>
using namespace std;

const int N=11;
int n,x,y,a[N][N],f[N+N][N][N];

int main(){
  cin>>n;
  while(cin>>x>>y>>a[x][y],x);
  
  for(int k=2; k<=n+n; k++) //走了k步
  for(int i=1; i<=n; i++)   //走到i行
  for(int x=1; x<=n; x++){  //走到x行
    int j=k-i,y=k-x;
    if(j>=1&&j<=n&&y>=1&&y<=n){
      f[k][i][x]=max(max(f[k-1][i-1][x-1],f[k-1][i-1][x]),
                     max(f[k-1][i][x-1],f[k-1][i][x]))+a[i][j]+a[x][y];
      if(i==x) f[k][i][x]-=a[i][j];
    }
  }
  cout<<f[n+n][n][n];
}