741. Cherry Pickup (Hard)

Description

741. Cherry Pickup (Hard)

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

Solution

This problem can be approached using dynamic programming, and although the concept is straightforward, there are several details to consider.

The process of picking cherries back and forth is equivalent to two individuals moving from $[0, 0]$ to $[n - 1, n - 1]$.

Let's use $k$ to represent the number of steps taken, $x_1$ to represent the current $x$ coordinate of the first person, and $x_2$ to represent the current $x$ coordinate of the second person. The current coordinates of the first and second persons can be calculated as $k - x_1$ and $k - x_2$, respectively.

$dp[k][x_1][x_2]$ represents the total number of cherries picked by the two persons after taking $k$ steps, with the first person at position $(x_1, k - x_1)$ and the second person at position $(x_2, k - x_2)$.

The state $(k, x_1, x_2)$ can be reached from four possible previous states: $(k - 1, x_1 - 1, x_2)$, $(k - 1, x_1 - 1, x_2 - 1)$, $(k - 1, x_1, x_2)$, and $(k - 1, x_1, x_2 - 1)$. Based on this, we can establish the following recurrence relation:

• If $x_1 = x_2$, then $dp[k][x_1][x_2] = dp[k - 1][prex_1][prex_2] + grid[x_1][y_1]$.
• Otherwise, $dp[k][x_1][x_2] = dp[k - 1][prex_1][prex_2] + grid[x_1][y_1] + grid[x_2][y_2]$.

$dp[k - 1][prex_1][prex_2]$ represents the maximum value among the four possible previous states. It's important to note that if a thorny bush is encountered, $dp[k][x_1][x_2]$ should be set to $-\infty$ instead of $0$ to indicate that the path is impassable.

Code

class Solution {
  public:
    int cherryPickup(vector<vector<int>> &grid) {
        int n = grid.size();
        vector<vector<vector<int>>> dp(2 * n + 1, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
        vector<vector<int>> mov{{-1, 0}, {-1, -1}, {0, -1}, {0, 0}};
        dp[0][0][0] = grid[0][0];
        for (int i = 1; i <= 2 * n - 2; ++i) {
            for (int x1 = 0; x1 <= i && x1 < n; ++x1) {
                for (int x2 = 0; x2 <= x1 && x2 < n; ++x2) {
                    int y1 = i - x1, y2 = i - x2;
                    if (y1 < 0 || y1 >= n || y2 < 0 || y2 >= n) {
                        continue;
                    }
                    if (grid[x1][i - x1] == -1 || grid[x2][i - x2] == -1) {
                        dp[i][x1][x2] = INT_MIN;
                        continue;
                    }
                    int tmp = INT_MIN; // tmp must be -infty
                    for (int j = 0; j < 4; ++j) {
                        int prex1 = x1 + mov[j][0], prey1 = i - 1 - prex1;
                        int prex2 = x2 + mov[j][1], prey2 = i - 1 - prex2;
                        if (prex1 < 0 || prex1 >= n || prey1 < 0 || prey1 >= n || prex2 < 0 || prex2 >= n || prey2 < 0 || prey2 >= n) {
                            continue;
                        }
                        if (grid[prex1][prey1] == -1 || grid[prex2][prey2] == -1) {
                            continue;
                        }
                        tmp = max(tmp, dp[i - 1][prex1][prex2]);
                    }
                    if (x1 == x2) {
                        dp[i][x1][x2] = max(dp[i][x1][x2], tmp + grid[x1][i - x1]);
                    } else {
                        dp[i][x1][x2] = max(dp[i][x1][x2], tmp + grid[x1][i - x1] + grid[x2][i - x2]);
                    }
                }
            }
        }
        return max(dp[2 * n - 2][n - 1][n - 1], 0);
    }
};