Cherry Pickup


  • 1

    Click here to see the full article post


  • 0
    Y

    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.


  • 0
    E

    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 write-ups. 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


  • 0

    @yren2 Corrected, thanks.
    @eggeggegg Thanks, appreciate it.


  • 0
    X

    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];
        }
    }
    

  • 0

    @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 re-update 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 re-update the state from bottom right to top left.


  • 0
    X

    @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:)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.