Leetcode 741: Cherry Pickup

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.

• 0 means the cell is empty, so you can pass through,
• 1 means the cell contains a cherry that you can pick up and pass through, or
• -1 means the cell contains a thorn that blocks your way.

Return the maximum number of cherries you can collect by following the rules below:

• Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
• After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
• When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
• If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

Example 1:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.

Example 2:

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• grid[i][j] is -1, 0, or 1.
• grid[0][0] != -1
• grid[n - 1][n - 1] != -1

Problem Analysis:

As the description, we start at position [0, 0], then move right or move down, until at the position [n-1, n-1], then move left or move up return to position [0, 0]. With this path, we compute the maximum cherries that we can pick up.

To simplify it, we can thought it as two paths from [0, 0] to [n-1, n-1] with moving right or moving down.

And we can get each path length is 2n-2. So if we iterate all paths, we must try 2^(4n-4) times. It’s too large.

So here we can thought it as two people each choose one path from [0,0] to [n-1,n-1]. As the path length is 2n-2, when in mth step, one people is at position [x1, y1], x1 + y1 = m, then another people at [x2, y2], x2 + y2 = m, we can get y2 = x1+y1-x2. So we can use dynamic programming, iterate compute the path step one by one, then finally we can get the answer.

Solution

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        vector<vector<vector<int>>> memory(grid.size(), 
          vector<vector<int>>(grid.size(), 
            vector<int>(grid.size(), numeric_limits<int>::min())));

        return max(0, visit(grid, memory, 0, 0, 0));
    }

    int visit(vector<vector<int>>& grid, vector<vector<vector<int>>>& memory,
               int x1, int y1, int x2) {
        int y2 = x1 + y1 - x2;
        if (x1 == grid.size() || y1 == grid.size() ||
           x2 == grid.size() || y2 == grid.size() ||
            grid[x1][y1] == -1 || grid[x2][y2] == -1)
            return -1000000;

        if (x1 == grid.size() - 1 && y1 == grid.size() - 1)
          return grid[x1][y1];

        if (memory[x1][y1][x2] != numeric_limits<int>::min())
          return memory[x1][y1][x2];

        int res = grid[x1][y1];
        if (x1 != x2) res += grid[x2][y2];
        res += max(max(visit(grid, memory, x1, y1 + 1, x2 + 1), 
                        visit(grid, memory, x1 + 1, y1, x2 + 1)), 
                    max(visit(grid, memory, x1, y1 + 1, x2), 
                        visit(grid, memory, x1 + 1, y1, x2)));
        memory[x1][y1][x2] = res;
        return res;
    }
};

Time complexity is O(n³)

Space complexity is O(n³)