MAXIMUM PATH SUM DP

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e3 + 5;
const int mod = 1e9 + 7;

ll dp[N][N] , a[N][N];
ll n , m ;
ll func(ll i , ll j)
{

    if( i == n - 1 && j == m - 1){
        dp[i][j] = a[i][j];
        return a[i][j];
    }
    if(dp[i][j] != -1)
        return  dp[i][j];

    if(i < n - 1  && j < m - 1)
    dp[i][j] = a[i][j] + max(func(i + 1 , j) , func(i , j + 1));
    else if(i == n - 1)
    dp[i][j] = a[i][j] + func(i , j + 1);
    else
    dp[i][j] = a[i][j] + func(i + 1 , j);
    return dp[i][j];

}

int main()
{
    fast;
    cin >> n >> m ;
    for(int i = 0 ; i < n ;i++ )
    {
        for(int j = 0  ; j < m ; j++ ){
            cin >> a[i][j];
            dp[i][j] = -1;
        }
    }
    cout << func(0,0);

    /*for(int i = n  - 1 ; i >= 0   ; i-- )
    {
        for(int j = m - 1 ; j >= 0 ; j-- )
        {

        if( i == n - 1 && j == m - 1)
            dp[i][j] = a[i][j];
        else if(i < n - 1  && j < m - 1)
            dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i][j+1]);
        else if(i == n - 1)
            dp[i][j] = a[i][j] + dp[i][j+1];
        else
            dp[i][j] = a[i][j] + dp[i+1][j];

        }
    }
    cout << dp[0][0];*/













    return 0;

}