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
34
class Solution {
 public:
  int cherryPickup(vector<vector<int>>& grid) {
    this->m = grid.size();
    this->n = grid[0].size();
    // dp[x][y1][y2] := max cherries we can collect w/
    // Robot #1 on (x, y1) and Robot #2 on (x, y2) first
    dp.resize(m, vector<vector<int>>(n, vector<int>(n, -1)));
    return cherryPick(grid, 0, 0, n - 1);
  }

 private:
  int m;
  int n;
  vector<vector<vector<int>>> dp;

  int cherryPick(const vector<vector<int>>& grid, int x, int y1, int y2) {
    if (x == m)
      return 0;
    if (y1 < 0 || y1 == n || y2 < 0 || y2 == n)
      return 0;
    if (dp[x][y1][y2] != -1)
      return dp[x][y1][y2];

    const int currRow = grid[x][y1] + (y1 != y2) * grid[x][y2];

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

    return dp[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
32
33
34
class Solution {
  public int cherryPickup(int[][] grid) {
    this.m = grid.length;
    this.n = grid[0].length;
    // dp[x][y1][y2] := max cherries we can collect w/
    // Robot #1 on (x, y1) and Robot #2 on (x, y2) first
    dp = new int[m][n][n];
    for (int[][] A : dp)
      Arrays.stream(A).forEach(a -> Arrays.fill(a, -1));
    return cherryPick(grid, 0, 0, n - 1);
  }

  private int m;
  private int n;
  private int[][][] dp;

  private int cherryPick(int[][] grid, int x, int y1, int y2) {
    if (x == m)
      return 0;
    if (y1 < 0 || y1 == n || y2 < 0 || y2 == n)
      return 0;
    if (dp[x][y1][y2] != -1)
      return dp[x][y1][y2];

    final 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)
        dp[x][y1][y2] =
            Math.max(dp[x][y1][y2], currRow + cherryPick(grid, x + 1, y1 + d1, y2 + d2));

    return dp[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] := max cherries we can collect w/
    // Robot #1 on (x, y1) and Robot #2 on (x, y2) first
    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] := max cherries we can collect w/
    // Robot #1 on (x, y1) and Robot #2 on (x, y2) first
    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];
  }
}