#55491: c++ 遞迴dp


61247091s@gapps.ntnu.edu.tw (wei)


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

int m, n;
int a[55][55];
int mem[55][55][55][55]; 
int cnt(int r1, int c1, int r2, int c2) {
    if (r1 >= m || c1 >= n || r2 >= m || c2 >= n) return -1e9;
    
    if (r1 == m - 1 && c1 == n - 1 && r2 == m - 1 && c2 == n - 1) {
        return 0;}

    if (mem[r1][c1][r2][c2] != -1) return mem[r1][c1][r2][c2];

    int reward = 0;
    if (r1 == r2 && c1 == c2)reward = a[r1][c1];
    else reward = a[r1][c1] + a[r2][c2];
 
    int path1 = cnt(r1 + 1, c1, r2 + 1, c2); 
    int path2 = cnt(r1 + 1, c1, r2, c2 + 1); 
    int path3 = cnt(r1, c1 + 1, r2 + 1, c2); 
    int path4 = cnt(r1, c1 + 1, r2, c2 + 1); 

    int max_next = max({path1, path2, path3, path4});
    
    // 6. 寫入筆記本,一輩子不擦掉!
    return mem[r1][c1][r2][c2] = max_next + reward;
}

int main() {
    cin >> m >> n;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)  cin >> a[i][j];}
    memset(mem, -1, sizeof(mem));
    cout << cnt(0, 0, 0, 0) << endl;
    
    return 0;
}