Skip to content

741. Cherry Pickup 👍

Approach 1: Top-down

  • Time: $O(n^3)$
  • Space: $O(n^3)$
 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
class Solution {
 public:
  int cherryPickup(vector<vector<int>>& grid) {
    // The problem is identical as two people start picking cherries
    // From grid[0][0] simultaneously
    n = grid.size();
    // dp[x1][y1][x2] := max cherries we could pick from
    // g[0][0] -> g[x1 - 1][y1 - 1] + g[0][0] -> g[x2 - 1][y2 - 1],
    // Where y2 = x1 + y1 - x2 (reduce states from 4 to 3)
    dp.resize(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MIN)));
    return max(0, cherryPickup(grid, 0, 0, 0));
  }

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

  int cherryPickup(const vector<vector<int>>& grid, int x1, int y1, int x2) {
    const int y2 = x1 + y1 - x2;
    if (x1 == n || y1 == n || x2 == n || y2 == n)
      return -1;
    if (x1 == n - 1 && y1 == n - 1)
      return grid[x1][y1];
    if (grid[x1][y1] == -1 || grid[x2][y2] == -1)
      return -1;
    int& ans = dp[x1][y1][x2];
    if (ans > INT_MIN)
      return ans;

    ans = max({cherryPickup(grid, x1 + 1, y1, x2),
               cherryPickup(grid, x1 + 1, y1, x2 + 1),
               cherryPickup(grid, x1, y1 + 1, x2),
               cherryPickup(grid, x1, y1 + 1, x2 + 1)});
    if (ans == -1)
      return ans;

    ans += grid[x1][y1];  // Do pick some cherries
    if (x1 != x2)         // Two people are on different grids
      ans += grid[x2][y2];

    return ans;
  }
};

 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
class Solution {
  public int cherryPickup(int[][] grid) {
    // The problem is identical as two people start picking cherries
    // From grid[0][0] simultaneously
    n = grid.length;
    dp = new Integer[n][n][n];
    return Math.max(0, cherryPickup(grid, 0, 0, 0));
  }

  private int n;

  // dp[x1][y1][x2] := max cherries we could pick from
  // g[0][0] -> g[x1 - 1][y1 - 1] + g[0][0] -> g[x2 - 1][y2 - 1],
  // Where y2 = x1 + y1 - x2 (reduce states from 4 to 3)
  private Integer[][][] dp;

  private int cherryPickup(int[][] grid, int x1, int y1, int x2) {
    final int y2 = x1 + y1 - x2;
    if (x1 == n || y1 == n || x2 == n || y2 == n)
      return -1;
    if (x1 == n - 1 && y1 == n - 1)
      return grid[x1][y1];
    if (grid[x1][y1] == -1 || grid[x2][y2] == -1)
      return -1;
    if (dp[x1][y1][x2] != null)
      return dp[x1][y1][x2];

    dp[x1][y1][x2] = Math.max(
        Math.max(cherryPickup(grid, x1 + 1, y1, x2), cherryPickup(grid, x1 + 1, y1, x2 + 1)),
        Math.max(cherryPickup(grid, x1, y1 + 1, x2), cherryPickup(grid, x1, y1 + 1, x2 + 1)));
    if (dp[x1][y1][x2] == -1)
      return dp[x1][y1][x2];

    dp[x1][y1][x2] += grid[x1][y1]; // Do pick some cherries
    if (x1 != x2)                   // Two people are on different grids
      dp[x1][y1][x2] += grid[x2][y2];

    return dp[x1][y1][x2];
  }
}

Approach 2: Bottom-up

  • Time: $O(n^3)$
  • Space: $O(n^3)$
 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 cherryPickup(vector<vector<int>>& grid) {
    const int n = grid.size();
    // dp[x1][y1][x2] := max cherries we could pick from
    // g[0][0] -> g[x1 - 1][y1 - 1] + g[0][0] -> g[x2 - 1][y2 - 1],
    // Where y2 = x1 + y1 - x2 (reduce states from 4 to 3)
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -1)));
    dp[1][1][1] = grid[0][0];

    for (int x1 = 1; x1 <= n; ++x1)
      for (int y1 = 1; y1 <= n; ++y1)
        for (int x2 = 1; x2 <= n; ++x2) {
          const int y2 = x1 + y1 - x2;
          if (y2 < 1 || y2 > n)
            continue;
          if (grid[x1 - 1][y1 - 1] == -1 || grid[x2 - 1][y2 - 1] == -1)
            continue;
          const int ans = max({dp[x1 - 1][y1][x2], dp[x1 - 1][y1][x2 - 1],
                               dp[x1][y1 - 1][x2], dp[x1][y1 - 1][x2 - 1]});
          if (ans < 0)
            continue;
          dp[x1][y1][x2] = ans + grid[x1 - 1][y1 - 1];
          if (x1 != x2)
            dp[x1][y1][x2] += grid[x2 - 1][y2 - 1];
        }

    return max(0, dp[n][n][n]);
  }
};

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

    // dp[x1][y1][x2] := max cherries we could pick from
    // g[0][0] -> g[x1 - 1][y1 - 1] + g[0][0] -> g[x2 - 1][y2 - 1],
    // Where y2 = x1 + y1 - x2 (reduce states from 4 to 3)
    int[][][] dp = new int[n + 1][n + 1][n + 1];
    for (int[][] A : dp)
      Arrays.stream(A).forEach(a -> Arrays.fill(a, -1));
    dp[1][1][1] = grid[0][0];

    for (int x1 = 1; x1 <= n; ++x1)
      for (int y1 = 1; y1 <= n; ++y1)
        for (int x2 = 1; x2 <= n; ++x2) {
          final int y2 = x1 + y1 - x2;
          if (y2 < 1 || y2 > n)
            continue;
          if (grid[x1 - 1][y1 - 1] == -1 || grid[x2 - 1][y2 - 1] == -1)
            continue;
          final int ans = Math.max(Math.max(dp[x1 - 1][y1][x2], dp[x1 - 1][y1][x2 - 1]),
                                   Math.max(dp[x1][y1 - 1][x2], dp[x1][y1 - 1][x2 - 1]));
          if (ans < 0)
            continue;
          dp[x1][y1][x2] = ans + grid[x1 - 1][y1 - 1];
          if (x1 != x2)
            dp[x1][y1][x2] += grid[x2 - 1][y2 - 1];
        }

    return Math.max(0, dp[n][n][n]);
  }
}