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

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

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