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.
    const int n = grid.size();
    vector<vector<vector<int>>> mem(
        n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MIN)));
    return max(0, cherryPickup(grid, 0, 0, 0, mem));
  }

 private:
  // Returns the maximum 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
  // (reducing states from 4 to 3).
  int cherryPickup(const vector<vector<int>>& grid, int x1, int y1, int x2,
                   vector<vector<vector<int>>>& mem) {
    const int n = grid.size();
    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& res = mem[x1][y1][x2];
    if (mem[x1][y1][x2] > INT_MIN)
      return res;

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

    res += grid[x1][y1];  // Pick some cherries.
    if (x1 != x2)         // Two people are on the different grids.
      res += grid[x2][y2];

    return res;
  }
};

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

  // Returns the maximum 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
  // (reducing states from 4 to 3).
  private int cherryPickup(int[][] grid, int x1, int y1, int x2, Integer[][][] mem) {
    final int n = grid.length;
    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;
    Integer res = mem[x1][y1][x2];
    if (res != null)
      return res;

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

    res += grid[x1][y1]; // Pick some cherries.
    if (x1 != x2)        // Two people are on the different grids.
      res += grid[x2][y2];

    return mem[x1][y1][x2] = res;
  }
}

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] := the maximum 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 (reducing 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] := the maximum 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 (reducing states from 4 to 3)
    int[][][] dp = new int[n + 1][n + 1][n + 1];
    for (int[][] A : dp)
      Arrays.stream(A).forEach(B -> Arrays.fill(B, -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]);
  }
}