闫式dp分析法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 55;

int f[N * 2][N][N];

int g[N][N];

int n , m;

int main() {

    cin >> n >> m;

    for (int i = 1 ; i <= n ; i ++ ) 
        for (int j = 1 ; j <= m ; j ++ ) 
            cin >> g[i][j];


    for (int k = 2; k <= n + m; k ++ )
        for (int i = max(1, k - m); i <= n && i < k; i ++ )
            for (int j = max(1, k - m); j <= n && j < k; j ++ )
                for (int a = 0; a <= 1; a ++ )
                    for (int b = 0; b <= 1; b ++ )
                    {
                        int t = g[i][k - i];
                        if (i != j || k == 2 || k == n + m) // 除了起点和终点之外，其余每个格子只能走一次
                        {
                            t += g[j][k - j];
                            f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                        }
                    }

    printf("%d\n", f[n + m][n][n]);

    return 0;

}