A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 741. Cherry Pickup, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, dynamic programming, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- DP, greedy
- WA
- 47 / 56 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are cherryPickup, dfs.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N^2), space: O(N^2)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DP, greedy
02//WA
03//47 / 56 test cases passed.
04/*
05two pass(forward and backward),
06in each pass, greedily maximize the profit it gets,
07but this doesn't work for the case:
08[[1,1,1,1,0,0,0],
09[0,0,0,1,0,0,0],
10[0,0,0,1,0,0,1],
11[1,0,0,1,0,0,0],
12[0,0,0,1,0,0,0],
13[0,0,0,1,0,0,0],
14[0,0,0,1,1,1,1]]
15where in the first pass,
16we shouldn't choose the path that will maximize the profit!
17*/
18//time: O(N^2), space: O(N^2)
19enum class DIR{
20 NONE = 0,
21 UP = 1,
22 LEFT = 2
23};
24
25class Solution {
26public:
27 int cherryPickup(vector<vector<int>>& grid) {
28 int n = grid.size();
29
30 if(n == 1) return max(grid[0][0], 0);
31
32 vector<vector<int>> dpf(n, vector<int>(n, 0));
33 vector<vector<int>> dpb(n, vector<int>(n, 0));
34 vector<vector<DIR>> from(n, vector<DIR>(n, DIR::NONE));
35
36 //base case
37 dpf[0][0] = grid[0][0];
38 grid[0][0] = 0;
39 for(int i = 0; i < n; ++i){
40 for(int j = 0; j < n; ++j){
41 if(grid[i][j] == -1){
42 dpf[i][j] = -1;
43 }else{
44 if(i-1 >= 0 && dpf[i-1][j] != -1){
45 if(dpf[i-1][j]+grid[i][j] > dpf[i][j]){
46 dpf[i][j] = dpf[i-1][j]+grid[i][j];
47 from[i][j] = DIR::UP;
48 }
49 }
50 if(j-1 >= 0 && dpf[i][j-1] != -1){
51 if(dpf[i][j-1]+grid[i][j] > dpf[i][j]){
52 dpf[i][j] = dpf[i][j-1]+grid[i][j];
53 from[i][j] = DIR::LEFT;
54 }
55 }
56 }
57 }
58 }
59
60 // cout << "dpf: " << endl;
61 // for(int i = 0; i < n; ++i){
62 // for(int j = 0; j < n; ++j){
63 // cout << dpf[i][j] << " ";
64 // }
65 // cout << endl;
66 // }
67 // cout << endl;
68
69 // cout << "from: " << endl;
70 // for(int i = 0; i < n; ++i){
71 // for(int j = 0; j < n; ++j){
72 // if(from[i][j] == DIR::NONE) cout << 0;
73 // else if(from[i][j] == DIR::LEFT) cout << 1;
74 // else cout << 2;
75 // cout << " ";
76 // }
77 // cout << endl;
78 // }
79 // cout << endl;
80
81 //go backward the path and update "grid"
82 // cout << "go backward: " << endl;
83 int i = n-1, j = n-1;
84 while(i != 0 || j != 0){
85 // cout << "(" << i << ", " << j << ")" << endl;
86 if(grid[i][j] > 0) grid[i][j] = 0;
87
88 //go to previous position
89 if(from[i][j] == DIR::LEFT){
90 --j;
91 }else if(from[i][j] == DIR::UP){
92 --i;
93 }else{
94 //no way to go back!
95 return 0;
96 }
97 }
98
99 // cout << "grid: " << endl;
100 // for(int i = 0; i < n; ++i){
101 // for(int j = 0; j < n; ++j){
102 // cout << grid[i][j] << " ";
103 // }
104 // cout << endl;
105 // }
106 // cout << endl;
107
108 for(int i = n-1; i >= 0; --i){
109 for(int j = n-1; j >= 0; --j){
110 if(dpf[i][j] == -1){
111 dpb[i][j] = -1;
112 }else{
113 if(i+1 < n && dpb[i+1][j] != -1){
114 dpb[i][j] = max(dpb[i+1][j]+grid[i][j], dpb[i][j]);
115 }
116 if(j+1 < n && dpb[i][j+1] != -1){
117 dpb[i][j] = max(dpb[i][j+1]+grid[i][j], dpb[i][j]);
118 }
119 }
120 }
121 }
122
123 // cout << "dpb: " << endl;
124 // for(int i = 0; i < n; ++i){
125 // for(int j = 0; j < n; ++j){
126 // cout << dpb[i][j] << " ";
127 // }
128 // cout << endl;
129 // }
130 // cout << endl;
131
132 return dpf[n-1][n-1] + dpb[0][0];
133 }
134};
135
136//Approach #2: Dynamic Programming (Top Down)
137//two players go from (0,0) to (N-1,N-1)
138//Runtime: 76 ms, faster than 56.33% of C++ online submissions for Cherry Pickup.
139//Memory Usage: 22.6 MB, less than 56.16% of C++ online submissions for Cherry Pickup.
140//time: O(N^3), space: O(N^3)
141class Solution {
142public:
143 int n;
144 vector<vector<vector<int>>> memo;
145
146 int dfs(vector<vector<int>>& grid, int r1, int c1, int r2){
147 //r1+r2 = c1+c2 -> c2 = r1+r2-c1
148 int c2 = r1+c1-r2;
149 //out of boundary
150 if(r1 >= n || c1 >= n || r2 >= n || c2 >= n){
151 return INT_MIN;
152 }
153 //cannot go to this cell
154 if(grid[r1][c1] == -1 || grid[r2][c2] == -1){
155 return INT_MIN;
156 }
157 //stop condition
158 if(r1 == n-1 && c1 == n-1){
159 //r2 and c2 will also be n-1, too!
160 return grid[n-1][n-1];
161 }
162 if(memo[r1][c1][r2] != INT_MIN){
163 return memo[r1][c1][r2];
164 }
165
166 int ans;
167
168 ans = grid[r1][c1];
169 //avoid add the same grid twice
170 if(r1 != r2) ans += grid[r2][c2];
171 ans += max({dfs(grid, r1+1, c1, r2+1), //p1, p2: down
172 dfs(grid, r1, c1+1, r2), //p1, p2: right, new_c2=r1+c1+1-r2=old_c2+1
173 dfs(grid, r1+1, c1, r2), //p1: down, p2: right, new_c2=old_c2+1=r1+c1-r2+1=r1+1+c1-new_r2
174 dfs(grid, r1, c1+1, r2+1)}); //p1: right, p2: down
175
176 return memo[r1][c1][r2] = ans;
177 };
178
179 int cherryPickup(vector<vector<int>>& grid) {
180 n = grid.size();
181
182 memo = vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
183
184 /*
185 if the return value is negative,
186 that means the path is invalid,
187 so no cherry to pick,
188 giving us profit = 0
189 */
190 return max(0, dfs(grid, 0, 0, 0));
191 }
192};
193
194//Approach #3: Dynamic Programming (Bottom Up)
195//use the concept of time
196//Runtime: 96 ms, faster than 38.22% of C++ online submissions for Cherry Pickup.
197//Memory Usage: 35.3 MB, less than 28.77% of C++ online submissions for Cherry Pickup.
198//time: O(N^3), space: O(N^2)
199class Solution {
200public:
201 int cherryPickup(vector<vector<int>>& grid) {
202 int n = grid.size();
203 vector<vector<int>> dp(n, vector<int>(n, INT_MIN));
204
205 //base case
206 dp[0][0] = grid[0][0];
207
208 //t: timestep, at time t, player 1 and 2 each move t steps
209 for(int t = 1; t <= 2*(n-1); ++t){
210 vector<vector<int>> dp_next(n, vector<int>(n, INT_MIN));
211
212 for(int r1 = 0; r1 < n; ++r1){
213 for(int r2 = 0; r2 < n; ++r2){
214 int c1 = t-r1, c2 = t-r2;
215 if(c1 < 0 || c1 >= n || c2 < 0 || c2 >= n) continue;
216 //cannot go to this cell, skip it
217 if(grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;
218 int ans = grid[r1][c1];
219 if(r1 != r2) ans += grid[r2][c2];
220
221 ans += max({
222 (r1-1>=0 && r2-1>=0) ? dp[r1-1][r2-1] : INT_MIN, //both from top
223 dp[r1][r2], //both comes from left
224 (r1-1>=0) ? dp[r1-1][r2] : INT_MIN, //p1 from top, p2 from left
225 (r2-1 >= 0) ? dp[r1][r2-1] : INT_MIN //p1 from left, p2 from top
226 });
227
228 dp_next[r1][r2] = ans;
229 }
230 }
231
232 swap(dp, dp_next);
233 }
234
235 return max(dp[n-1][n-1], 0);
236 }
237};Cost
Complexity
Time
O(N^2), space: O(N^2)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.