Pass note 【 dynamic planning 】

Pass slip 【 Dynamic programming 】

Title Description

AC Code

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

int n,m;            // That's ok 、 Column 
int a[55][55], dp[105][55][55];

signed main(){
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
    
        for (int j = 1; j <= m; ++j) {
    
            cin>>a[i][j];
        }
    }
    memset(dp, 0, sizeof dp);       // initialization 
    for (int i = 2; i <= n + m; ++i) {
          // The horizontal and vertical coordinates add up to i The diagonal of 
        for (int y1 = 1; y1 <= m && y1 < i; ++y1) {
      // The ordinate of the first point 
            for (int y2 = 1; y2 <= m && y2 < i ; ++y2) {
        // The ordinate of the second point 
                dp[i][y1][y2] = max(max(dp[i - 1][y1][y2],dp[i - 1][y1 - 1][y2 - 1]),
                                    max(dp[i - 1][y1 - 1][y2],dp[i - 1][y1][y2 - 1]));
                dp[i][y1][y2] += a[i - y1][y1];
                if(y1 != y2)
                    dp[i][y1][y2] += a[i - y2][y2];
            }
        }
    }
    cout<<dp[n + m][m][m];
    return 0;
}

/* 3 3 0 3 9 2 8 5 5 7 0 34 */