Sponsored
Sponsored
We will approach the problem using dynamic programming by maintaining a 3D DP table. The idea is to simulate two individuals traversing the grid simultaneously: one moving from (0,0) to (n-1,n-1) and the other returning from (n-1,n-1) back to (0,0). Both will walk through cells to collect cherries with the understanding that a cell’s cherry can be collected only once.
The DP table, dp[x1][y1][x2], represents the maximum cherries collected when person 1 is at (x1,y1) and person 2 is at (x2,y1+x1-x2) such that both paths have used same number of steps. Transitions are explored based on valid grid movements (right or down) and allowed combinations.
This method ensures we utilize optimal substructure and memoization to avoid computing the same state multiple times.
Time Complexity: O(n^3), due to iterating through each position combination for both players.
Space Complexity: O(n^3), the space needed to store results of all position combinations.
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8 int cherryPickup(vector<vector<int>>& grid) {
9 int n = grid.size();
10 vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
11 dp[0][0][0] = grid[0][0];
12
13 for (int x1 = 0; x1 < n; ++x1) {
14 for (int y1 = 0; y1 < n; ++y1) {
15 for (int x2 = 0; x2 < n; ++x2) {
16 int y2 = x1 + y1 - x2;
17 if (y2 < 0 || y2 >= n || grid[x1][y1] == -1 || grid[x2][y2] == -1) {
18 continue;
19 }
20
21 int cherries = grid[x1][y1];
22 if (x1 != x2) {
23 cherries += grid[x2][y2];
24 }
25
26 if (x1 > 0) {
27 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1-1][y1][x2] + cherries);
28 }
29 if (y1 > 0) {
30 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1-1][x2] + cherries);
31 }
32 if (x2 > 0) {
33 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1][x2-1] + cherries);
34 }
35 if (y2 > 0) {
36 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1][x2] + cherries);
37 }
38 }
39 }
40 }
41
42 return max(0, dp[n-1][n-1][n-1]);
43 }
44};The C++ solution is similar to the previous implementations, employing a 3D vector to calculate and save intermediate results for the amount of cherries collected. The vector enables efficient access and update across recursive computations, ensuring path-only valid states are considered, leveraging direct memory access benefits in C++.
Given the constraints of the initial approach, further space optimization can be applied by minimizing the dimensions that are updated in the DP table at any given time. We'll reduce our 3D DP array into a 2D array considering only necessary state information, as they relate to specific grid traversals. This lowering of space dimensions capitalizes on the symmetrical nature of path reversals without sacrificing calculation correctness or granularity.
Time Complexity: O(n^3), iterating through elements optimized per journey line level.
Space Complexity: O(n^2), condensing memos to one comprehensive 2D table pairing.
1def cherryPickup(grid):
2 n = len(grid)
This solution keeps updating the 2D DP table along each step of a journey, maintaining only pertinent states per each t (sum of (x1 + y1)) layer. This slimmed-down model reduces memory burden significantly by recycling layers in place of ever-expanding a 3D matrix, aligning closely with each movement's iterative aspect.