超详细题解+代码

求点赞，题解在代码里面有写注释，关键代码的作用一目了然

#include <bits/stdc++.h>
using namespace std;

// dp[i][j][u][v]-->路径1走到(i,j)，路径2走到(u,v)时最大价值(必须夯） 
int dp[55][55][55][55]; 
int a[105][105]; // 存储每格价值

int main(){
    int n,m;
    cin >> n >> m;
    // 读入网格数据
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    // 四循动规（太带派了，必须夯） 
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int u = 1; u <= n; u++){
                // 保证路径不交叉：路径2的列v must 大于第路径1的列j
                for (int v = j + 1; v <= m; v++){
                    // 状态转移---考虑四种组合
                    dp[i][j][u][v] = max(
                        max(dp[i-1][j][u-1][v], dp[i-1][j][u][v-1]), 
                        max(dp[i][j-1][u-1][v], dp[i][j-1][u][v-1])
                    ) + a[i][j] + a[u][v]; // 加上当前两格价值
                }
            }
        }
    }
    // 终点是(n,m)并且两条路径不能重合，路径1终点是(n,m-1)，路径2终点是(n-1,m)
    cout << dp[n][m-1][n-1][m];
}