参考大神题解
//一个从正下方到结果的左 正右边到结果的上
//两人的下标不能相同
//走 n + m - 1 步
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int n, m;
int w[N][N];
int f[N * 2][N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
cin >> w[i][j];
//f[k, i, j]
//只有一步是在起点
for(int k = 2; k <= n + m; ++ k)
//看需不需要向右走
//i j 都是横坐标
for(int i = max(1, k - m); i <= n && i < k; ++ i)
for(int j = max(1, k - m); j <= n && j < k; j ++ )
//四个方向 下下 下右 右下 右右
if(i != j)
for(int a = 0; a <= 1; a ++ )
for(int b = 0; b <= 1; ++ b)
{
//f[k, i, j]
//都少走一步,从上一步转移 i j都是横坐标 + 当前
//后面的会先被遍历
//f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
}
//刚好在 一个正上方 一个正左方 还有一步不用走, 也走不到
printf("%d\n", f[n+m-1][n][n-1]);
return 0;
}