$\color{blue}{线性DP}$

状态转移 f(k,i,j) = (i==j)?w[i,k-i]:w[i,k-i]+w[i,k-j]+max(f(k-1,i,j),f(k-1,i-1,j),f(k-1,i,j-1),f(k-1,i-1,j-1))

时间复杂度 $O(n^3)$

$\color{green}{Code-cpp}$

#include<bits/stdc++.h>
#define For(i,x,y) for(int i = x;i<y;++i)
#define _for(i,x,y) for(int i = x;i<=y;++i)
using namespace std;
const int N = 55;
int w[N][N],f[N+N][N][N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    _for(i,1,n)
        _for(j,1,m)scanf("%d",&w[i][j]);
    _for(k,2,n+m)
        _for(i,1,n)
            _for(j,1,n)
                _for(a,0,1)
                    _for(b,0,1)
                        if(i<k&&j<k)f[k][i][j] = max(f[k][i][j],f[k-1][i-a][j-b]+(i==j?w[i][k-i]:w[i][k-i]+w[j][k-j]));
    printf("%d",f[n+m][n][n]);
    return 0;
}