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