Cherry Pickup LeetCode solution in C++

1
class Solution {
2
 public:
3
  int solve(int r1, int c1, int r2, vector<vector<int>> &grid, vector<vector<vector<int>>> &dp) {
4
    // Calculating c2 :
5
    /*
6
    (r1 + c1) = (r2 + c2)
7
    c2 = (r1 + c1) - r2
8
    */
9
    int c2 = (r1 + c1) - r2;
10

11
    // Base condition
12
    if (r1 >= grid.size() || r2 >= grid.size() || c1 >= grid[0].size() || c2 >= grid[0].size() ||
13
        grid[r1][c1] == -1 || grid[r2][c2] == -1) {
14
      return INT_MIN;
15
    }
16
    if (r1 == grid.size() - 1 && c1 == grid[0].size() - 1) {
17
      return grid[r1][c1];
18
    }
19

20
    if (dp[r1][c1][r2] != -1) {
21
      return dp[r1][c1][r2];
22
    }
23
    int ch = 0;
24
    if (r1 == r2 && c1 == c2) {
25
      ch += grid[r1][c1];
26
      // if both players are at the same place than collect cherry only one
27
      // time.
28
    } else {
29
      ch += grid[r1][c1] + grid[r2][c2];
30
    }
31
    cout << ch << "\n";
32

33
    // Trying all the possible paths for both the players
34

35
    int hh = solve(r1, c1 + 1, r2, grid, dp);
36
    int vh = solve(r1 + 1, c1, r2, grid, dp);
37
    int vv = solve(r1 + 1, c1, r2 + 1, grid, dp);
38
    int hv = solve(r1, c1 + 1, r2 + 1, grid, dp);
39

40
    // collecting maximum cherries from possible paths
41
    ch += max(max(hh, vh), max(vv, hv));
42

43
    dp[r1][c1][r2] = ch;
44

45
    return ch;
46
  }
47

48
  int cherryPickup(vector<vector<int>> &grid) {
49
    int n = grid.size();
50

51
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, -1)));
52

53
    int ans = solve(0, 0, 0, grid, dp);
54

55
    if (ans == INT_MIN || ans < 0) {
56
      return 0;
57
    }
58

59
    return ans;
60
  }
61
};