Cherry Pickup LeetCode solution in Java

1
class Solution {
2
  public int cherryPickup(int[][] grid) {
3
    int m = grid.length, n = grid[0].length;
4
    // For O(N^3) Dp sapce solution
5
    dp2 = new Integer[m][n][m];
6
    int ans = solve2(0, 0, 0, grid, 0, m, n);
7
    if (ans == Integer.MIN_VALUE) return 0;
8
    return ans;
9
  }
10

11
  private Integer[][][] dp2;
12

13
  private int solve2(int x1, int y1, int x2, int[][] g, int cpsf, int m, int n) {
14
    int y2 = x1 + y1 + -x2;
15
    if (x1 >= m || x2 >= m || y1 >= n || y2 >= n || g[x1][y1] == -1 || g[x2][y2] == -1)
16
      return Integer.MIN_VALUE;
17
    if (x1 == m - 1 && y1 == n - 1) return g[x1][y1];
18
    // If both p1 and p2 reach (m-1,n-1)
19
    if (dp2[x1][y1][x2] != null) return dp2[x1][y1][x2];
20
    int cherries = 0;
21
    // If both p1 and p2 are at same position then we need to add the cherry only once.
22
    if (x1 == x2 && y1 == y2) {
23
      cherries += g[x1][y1];
24
    }
25
    // If p1 and p2 are at different positions then repective cherries can be added.
26
    else {
27
      cherries += g[x1][y1] + g[x2][y2];
28
    }
29
    // 4 possibilites for p1 and p2 from each point
30
    int dd = solve2(x1 + 1, y1, x2 + 1, g, cpsf + cherries, m, n); // both moves down
31
    int dr = solve2(x1 + 1, y1, x2, g, cpsf + cherries, m, n); // p1 moves down and p2 moves right
32
    int rr = solve2(x1, y1 + 1, x2, g, cpsf + cherries, m, n); // both moves right
33
    int rd =
34
        solve2(x1, y1 + 1, x2 + 1, g, cpsf + cherries, m, n); // p1 moves right and p2 moves down
35

36
    // We take maximum of 4 possiblities
37
    int max = Math.max(Math.max(dd, dr), Math.max(rr, rd));
38
    if (max == Integer.MIN_VALUE) return dp2[x1][y1][x2] = max;
39
    return dp2[x1][y1][x2] = cherries += max;
40
  }
41
}