A 3D DP problem

What we need are:

  • A’s location, B’ location, A + B ‘s current value
  • A and B’s moving directions
  • Special case where a and b share the same location.
const int  ROW = 71, COL = 71;
int memo[ROW][COL][COL];
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
memset(memo, -1, sizeof memo);
const int n = grid.size(), m = grid[0].size();
memo[0][0][m-1] = grid[0][0] + grid[0][m-1];
int ret = memo[0][0][m - 1];
for (int i = 0; i < n - 1; ++i){
for (int a = 0; a< m; ++a){
for (int b = 0; b < m; ++b){
for (int aj = -1; aj <= 1; aj++){
for (int bj = -1; bj <= 1; bj++){
if (memo[i][a][b] == -1)continue;
int val = memo[i][a][b];
int newa = a + aj, newb = b + bj;
if (newa < 0 || newa >= m || newb <0 || newb >= m) continue;
if (newa == newb){
memo[i+1][newa][newb] = max(memo[i+1][newa][newb], val + grid[i+1][newa]);
} else {
memo[i+1][newa][newb] = max(memo[i+1][newa][newb], val + grid[i+1][newa] + grid[i+1][newb]);
}
ret = max(ret, memo[i+1][newa][newb]);
}
}
}
}
}
return ret;
}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store