Skip to content

1463. Cherry Pickup II 👍

Approach 1: Top-down

  • Time: $O(mn^2)$
  • Space: $O(mn^2)$
 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
class Solution {
 public:
  int cherryPickup(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<vector<int>>> mem(m,
                                    vector<vector<int>>(n, vector<int>(n, -1)));
    return cherryPickup(grid, 0, 0, n - 1, mem);
  }

 private:
  // Returns the maximum cherries we can collect, where the robot #1 is on
  // (x, y1) and the robot #2 is on (x, y2).
  int cherryPickup(const vector<vector<int>>& grid, int x, int y1, int y2,
                   vector<vector<vector<int>>>& mem) {
    if (x == grid.size())
      return 0;
    if (y1 < 0 || y1 == grid[0].size() || y2 < 0 || y2 == grid[0].size())
      return 0;
    if (mem[x][y1][y2] != -1)
      return mem[x][y1][y2];

    const int currRow = grid[x][y1] + (y1 == y2 ? 0 : 1) * grid[x][y2];

    for (int d1 = -1; d1 <= 1; ++d1)
      for (int d2 = -1; d2 <= 1; ++d2)
        mem[x][y1][y2] =
            max(mem[x][y1][y2],
                currRow + cherryPickup(grid, x + 1, y1 + d1, y2 + d2, mem));

    return mem[x][y1][y2];
  }
};

 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
class Solution {
  public int dp(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int[][][] mem = new int[m][n][n];

    for (int[][] A : mem)
      Arrays.stream(A).forEach(B -> Arrays.fill(B, -1));

    return dp(grid, 0, 0, n - 1, mem);
  }

  // Returns the maximum cherries we can collect, where robot #1 is on (x, y1)
  // and robot #2 is on (x, y2).
  private int dp(int[][] grid, int x, int y1, int y2, int[][][] mem) {
    if (x == grid.length)
      return 0;
    if (y1 < 0 || y1 == grid[0].length || y2 < 0 || y2 == grid[0].length)
      return 0;
    if (mem[x][y1][y2] != -1)
      return mem[x][y1][y2];

    final int currRow = grid[x][y1] + (y1 == y2 ? 0 : grid[x][y2]);

    for (int d1 = -1; d1 <= 1; ++d1)
      for (int d2 = -1; d2 <= 1; ++d2)
        mem[x][y1][y2] = Math.max(mem[x][y1][y2], currRow + dp(grid, x + 1, y1 + d1, y2 + d2, mem));

    return mem[x][y1][y2];
  }
}

Approach 2: Bottom-up

  • Time: $O(mn^2)$
  • Space: $O(mn^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int cherryPickup(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    // dp[x][y1][y2] := the maximum cherries we can collect, where the robot #1
    // is on (x, y1) and the robot #2 is on (x, y2)
    vector<vector<vector<int>>> dp(m + 1,
                                   vector<vector<int>>(n, vector<int>(n)));

    for (int x = m - 1; x >= 0; --x)
      for (int y1 = 0; y1 < n; ++y1)
        for (int y2 = 0; y2 < n; ++y2) {
          const int currRow = grid[x][y1] + (y1 != y2) * grid[x][y2];
          for (int d1 = max(0, y1 - 1); d1 < min(n, y1 + 2); ++d1)
            for (int d2 = max(0, y2 - 1); d2 < min(n, y2 + 2); ++d2)
              dp[x][y1][y2] = max(dp[x][y1][y2], currRow + dp[x + 1][d1][d2]);
        }

    return dp[0][0][n - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int cherryPickup(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    // dp[x][y1][y2] := the maximum cherries we can collect, where the robot #1
    // is on (x, y1) and the robot #2 is on (x, y2)
    int[][][] dp = new int[m + 1][n][n];

    for (int x = m - 1; x >= 0; --x)
      for (int y1 = 0; y1 < n; ++y1)
        for (int y2 = 0; y2 < n; ++y2) {
          final int currRow = grid[x][y1] + (y1 == y2 ? 0 : 1) * grid[x][y2];
          for (int d1 = Math.max(0, y1 - 1); d1 < Math.min(n, y1 + 2); ++d1)
            for (int d2 = Math.max(0, y2 - 1); d2 < Math.min(n, y2 + 2); ++d2)
              dp[x][y1][y2] = Math.max(dp[x][y1][y2], currRow + dp[x + 1][d1][d2]);
        }

    return dp[0][0][n - 1];
  }
}