首先转换一下问题，原问题就等价于从找两条从$(1,1)$到$(n,m)$的互不相交的路径，使得路径上数值的和最大。
首先考虑令$f[i,j,k,l]$表示两条路径到$(i,j)$于$(k,l)$时的最大夹着，这时候我们发现，如果知道了“走”了多少步，那么只要知道横坐标（或纵坐标），就能根据走的步数算出令一个坐标，一举两等，大大简化状态转移。
于是我们令$f[k,i,j]$表示当走了k步，第一张纸条到第i行，第二张纸条到第j行时的最大价值。
于是状态转移方程为：
$f[k,i,j]=max{f[k-1][i][j](两个都向右走),f[k-1][i][j-1],f[k-1][i-1][j](一个向右一个向下),f[i-1][i-1][j-1](都向下走)}$
注意循环对i,j的时候，j从i+1开始（为了保证路径不重合，也可以做到不重不漏）。
附上代码：
#include<bits/stdc++.h> using namespace std; int a[60][60],f[101][60][60]; int n,m; int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&a[i][j]); for(int k=2;k<=n+m-1;++k){ for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(!(k-i+1) || !(k-j+1) ||(k-i+1>m+1) || (k-j+1)>m+1) continue;//有效位置 f[k][i][j]=max(f[k-1][i-1][j-1],f[k-1][i][j]); f[k][i][j]=max(f[k][i][j],max(f[k-1][i][j-1],f[k-1][i-1][j]))+a[i][k-i+1]+a[j][k-j+1]; } } } printf("%d",f[n+m-1][n-1][n]); return 0; }
原文：https://www.cnblogs.com/Asika3912333/p/11625171.html