Description Link to heading

741. Cherry Pickup (Hard)

Solution Link to heading

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 Link to heading 

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