-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy path1463
35 lines (25 loc) · 878 Bytes
/
1463
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
class Solution {
public:
int dy[3] = {0,-1,1};
int memo[71][71][71];
int dfs(vector<vector<int>>& grid, int i, int c1, int c2, int m, int n){
if(i==m)return 0;
if(c1<0 || c2<0 || c1>=n || c2>=n) return INT_MIN;
if(memo[i][c1][c2] != -1) return memo[i][c1][c2];
int ans = 0;
for(int k =0;k<3;k++){
for(int r = 0;r<3;r++){
ans = max(ans, dfs(grid, i+1, c1 + dy[k], c2 + dy[r] , m, n));
}
}
ans += (c1==c2) ? grid[i][c1] : grid[i][c1] + grid[i][c2];
return memo[i][c1][c2] = ans;
}
int cherryPickup(vector<vector<int>>& grid) {
int m = grid.size(); //rows
if(!m)return 0;
int n = grid[0].size(); //cols
memset(memo,-1,sizeof memo);
return dfs(grid,0,0,n-1,m,n);
}
};