Create a new version of paste:

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

int startMining(int row, int col, vector<vector<int> > &mine, vector<vector<int> > &memo){
    if(row < 0 || row >= mine.size() || col >= mine.size()){
        return 0;
    }
    
    //memo check
    if(memo[row][col] != 0){
        return memo[row][col];
    }
    /*
    Levels/States = Each Cell
    Options/Transitions = 3 options (i - 1, j + 1), (i, j + 1), (i + 1, j + 1)
    */
    int upperRight = startMining(row - 1, col + 1, mine, memo);
    int right = startMining(row, col + 1, mine, memo);
    int lowerRight = startMining(row + 1, col + 1, mine, memo);
    
    return memo[row][col] = mine[row][col] +  max(upperRight, max(right, lowerRight));
}


int startMiningDP(vector<vector<int> > &mine){
    //Storage & Meaning -  dp[i][j] = maximum gold that can be collected if we started from the ith wall and ended on jth wall
    int n = mine.size();
    int m = mine[0].size();
    vector<vector<int> > dp(n, vector<int>(m, 0));
    
    // Direction - Smallest Problem = dp[i][m - 1] = if we were on the right wall (analyse recursive calls)
    // for computing dp[i][j] = we should have answers to dp[i - 1][j + 1], dp[i][j + 1], dp[i + 1][j + 1];
    // So that means we should be starting from right wall(smallest case), as for any column j, we should already have answer for j + 1, as seen above in recursive calls
    
    // Smallest Problem (The maximum gold that we can get if we are on the right wall, is the gold present in that mine cell) as after collecting the gold from that cell, we move on to next column, which will out of bounds.
    // Also you can think of smallest problem from - 
    // Original Problem = Start on left wall (0th column) & End on right wall(m - 1)th column, what is the maximum
    // Smallest Problem = Start on the right wall(m - 1)th column, & End on right wall (m - 1)th column, what is the maximum gold that we can get
    for(int i = 0; i < n; i++){
        dp[i][m - 1] = mine[i][m - 1];
    }
    
    // Travel & Solve - As we figured out the smallest problem is at the right wall and largest problem is at left wall, we will traverse from right wall to left wall
    // Try all the 3 options for each cell to figure out the optimal value for each cell
    int maxGold = 0;
    for(int j = m - 2; j >= 0; j--){
        for(int i = 0; i < n; i++){
            int upperRight = 0, right = 0, lowerRight = 0;
            
            //only call if we aren't in 0th row
            if(i != 0){
                upperRight = dp[i - 1][j + 1];
            }
            
            //only call if we aren't in the (n - 1)th row
            if(i < n - 1){
                lowerRight = dp[i + 1][j + 1];
            }
            // this is always in bound 
            right = dp[i][j + 1];
            
            dp[i][j] = mine[i][j] + max(upperRight, max(right, lowerRight));
            // We reached the left wall by filling from right to left, when we reach 0th column, it is the original problem
            // But we need the maximum of the values in 0th column, as we could have started on any row on the left wall
            if(j == 0){
                maxGold = max(maxGold, dp[i][0]);
            }
        }
    }
    return maxGold;
    
}

int main() {
	// your code goes here
    int n, m;
    cin >> n >> m;
    vector<vector<int> > mine(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> mine[i][j];
        }
    }
    vector<vector<int> > memo(n, vector<int>(m, 0));
    int maxGold = INT_MIN;
    for(int i = 0; i < n; i++){
         maxGold = max(maxGold, startMining(i, 0, mine, memo));
    }
    cout << maxGold << '\n';
    cout << startMiningDP(mine) << '\n';
}

/*
6 6
0 1 4 2 8 2
4 3 6 5 0 4
1 2 4 1 4 6
2 0 7 3 2 2
3 1 5 9 2 4
2 7 0 8 5 1


10 10
23 87 56 14 98 69 35 90 47 62
6 72 91 31 80 25 53 39 18 66
77 61 10 42 58 85 95 21 36 74
40 12 63 89 17 50 99 68 29 26
81 33 52 96 45 19 13 43 59 3
9 16 97 24 65 32 7 30 55 71
44 84 92 1 73 37 22 93 20 34
67 5 11 64 28 46 70 38 94 15
2 76 48 60 8 57 41 49 27 75
88 100 4 78 83 51 86 79 19 54


*/