A 3D DP problem

1463. Cherry Pickup II

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