A 3D DP problem

This problem looks hard at the beginning, however, if you read it carefully and figure our all possible things that can define the unique states, you will find the solution.

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.

Here is a bottom up solution for reference. Although it has 5 layer for loops, the last two layer each one at has 3 value, the last two only 3*3. So the total complexity is O(ROW*COL*COL).

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;
}
};

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Here is how to authenticate users using Vue.js and Firebase

Three Flavors of React CSS

How to setup ESLint for your next project

how to setup ESLint for your next project nickang blog banner

How JavaScript works: the “this” variable and the execution context

Simple but often forgotten Javascript function

Solving a Hash Table Problem Through a JavaScript Lens: Observations of a Bootcamp Grad

ReasonML: Installation Guide for VS Code

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
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Leetcode Q386. Lexicographical Numbers (Q316)

Leetcode Q343. Integer Break (Q288)

[ 3, 3, 5, 5, 6, 7 ] Q239. Sliding Window Maximum (Q231)

Leetcode Q397. Integer Replacement (Q337)