Cherry Pickup


Hi @awice,
I think there is a typo in Approach #3 Java code.
Please change "ni" to "pi" and "nj" in "pj" in line 17 and 18.

I've noticed that you've been doing all of the editorial solutions for the contest problems and wanted to say thank you for all of these great solution writeups. I love reading these after struggling through the problems during the contest  you present very well written and easily digestible analyses. Thank you for your time


For solution 3, do we have to set the whole matrix to 1 at the start of each iteration?
Here is my code inspired by solution 3. It passes all current test cases. But I am not sure if it is correct.class Solution { public int cherryPickup(int[][] grid) { int n = grid.length; int[][] state = new int[n][n]; state[0][0] = grid[0][0]; for (int i = 0; i < n; i++) { Arrays.fill(state[i], 1); } state[0][0] = grid[0][0]; for (int m = 1; m < 2 * n  1; m++) { for (int i = Math.min(m, n  1); i >= Math.max(0, m  n + 1); i) { int j = m  i; for (int k = i; k >= Math.max(0, m  n + 1); k) { int l = m  k; if (grid[i][j] == 1  grid[k][l] == 1) { state[i][k] = 1; continue; } if (i > 0 && l > 0) { state[i][k] = Math.max(state[i][k], state[i  1][k]); } if (i > 0 && k > 0) { state[i][k] = Math.max(state[i][k], state[i  1][k  1]); } if (j > 0 && l > 0) { state[i][k] = Math.max(state[i][k], state[i][k]); } if (j > 0 && k > 0) { state[i][k] = Math.max(state[i][k], state[i][k  1]); } if (state[i][k] == 1) { continue; } state[i][k] += (i == k) ? grid[i][j] : grid[i][j] + grid[k][l]; // System.out.println(i + ", " + j + ", " + k + ", " + l + ": " + state[i][k]); } } } return state[n  1][n  1] == 1 ? 0 : state[n  1][n  1]; } }

@xh2277 I think your solution is correct, and it's a good idea.
Look at say, t = 2. We have possible coordinates (r1,c1) = (2,0), (1,1) and (0,2) for a single person. For two people, they can be represented by nine different (c1,c2). [ (0, 1, 2) x (0, 1, 2) where x is the cartesian product.] If we reupdate the state from bottom right to top left, we should be fine.
What about when the possible coordinates shrinks? If say N = 3, then for t = 3 with (2, 1), (1, 2), the possible (c1, c2) are only (1, 2). Investigating that, it remains okay to reupdate the state from bottom right to top left.

@awice
I think I get your point. Appreciate your reply. I think for me it is hard to come up with this solution in a real interview and prove it is correct. Maybe I will try the second approach with more space complexity:)