Cherry Pickup

2025-05-02

leetcode, 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.

cherry-pickup.png

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int steps = n * 2 - 1;

        int[][][] dp = new int[steps][n][n];
        for (int i = 0; i < steps; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], Integer.MIN_VALUE);
            }
        }
        dp[0][0][0] = grid[0][0];
        for (int step = 1; step < steps; step++) {
            for (int r1 = 0; r1 < n; r1++) {
                for (int r2 = 0; r2 < n; r2++) {
                    int c1 = step - r1;
                    int c2 = step - r2;

                    // 越界，超出网格
                    if (c1 < 0 || c1 >= n || c2 < 0 || c2 >= n) {
                        continue;
                    }

                    // 边界条件，触碰到障碍物
                    if (grid[r1][c1] == -1 || grid[r2][c2] == -1) {
                        continue;
                    }

                    int bestPrev = Integer.MIN_VALUE;

                    // 两人同时向下
                    if (r1 > 0 && r2 > 0) {
                        bestPrev = Math.max(bestPrev, dp[step - 1][r1 - 1][r2 - 1]);
                    }
                    // 人1向下，人2向右
                    if (r1 > 0) {
                        bestPrev = Math.max(bestPrev, dp[step - 1][r1 - 1][r2]);
                    }
                    // 人1向右，人2向下
                    if (r2 > 0) {
                        bestPrev = Math.max(bestPrev, dp[step - 1][r1][r2 - 1]);
                    }
                    // 两人同时向右
                    bestPrev = Math.max(bestPrev, dp[step - 1][r1][r2]);

                    if (bestPrev == Integer.MIN_VALUE) {
                        continue;
                    }

                    int cherries = bestPrev + grid[r1][c1];
                    if (r1 != r2) {
                        cherries += grid[r2][c2];
                    } else {
                        // 两人走到同一个格子，不作记录
                    }

                    dp[step][r1][r2] = cherries;
                }
            }
        }
        return Math.max(0, dp[steps - 1][n - 1][n - 1]);
    }
}

转化为双人路径

两人同时从(0,0)出发到(N-1,N-1)，两人的路径可以看作是一次往返路径的拆分。

动态规划状态定义

定义一个三维动态规划数组dp[k][x1][x2]，表示两个人分别走到(x1,k-x1)和(x2, k-x2)时，能够摘到的最大樱桃数。

  • 这里k表示两个人总共走的步数。
  • y1 = k - x1和y2 = k - x2是两个人在网格中的纵坐标。

状态转移方程
两个人每次可以选择向右或向下移动，因此共有4种移动组合：

  • 人1向右，人2向右
  • 人1向右，人2向下
  • 人1向下，人2向右
  • 人1向下，人2向下