# 10-liner DP with time/space optimization and why greedy doesn't work

• First of all, greedy method does not work here. That is:

Maximizing the first one-way for cherries does NOT guarantee maximized cherries for round-trip.

The reason is that the problem allows only shortest path moving and greedy method does not do a good overall planning.

Counter Example:
`0` 1 -1
`1 1` -1
1 `1 0`

If the first one-way goes along the red path for maximal 3 cherries, it splits the remaining 2 cherries into opposite sides of the diagonal which is impossible for round trip to pick up all cherries.

Define DP variable: so we have to plan the round trip altogether. Note that the path direction is irrelevant to the problem and we are forced to move only on shortest paths.

Define

`dp[i][j][L]` = the max cherries picked up from `(0,0)` along two shortest paths reaching `(i,L-i)` and `(j,L-j)`, respectively.

Note that each path length is exactly `L`, so the answer is to compute `dp[n-1][n-1][2*(n-1)]`.

To reach cells `(i,L-i)` and `(j,L-j)`, you have to reach their left or top cells with any combination, which leads to the DP equation:

``````dp[i][j][L] = max(dp[i-a][j-b][L-1] for a, b = 0 or 1) + grid[i][L-i] + grid[j][L-j]
``````

To optimize time/space complexity, note that

• `(i,j)` is symmetric, so why not just compute for `i<=j`.
• `(i,j,L)` has constraint: `max(L-n+1,0) <= i <= j <= min(L,n-1)`.
• `dp[][][L]` depends on only `dp[][][L-1]`, so no need to allocation `O(n)` space in `L` dimension.
``````int cherryPickup(vector<vector<int>>& grid)
{
int n = grid.size();
vector<vector<int>> cur(n, vector<int>(n,-1)), next = cur;
cur[0][0] = grid[0][0];

// cur[i][j] is set for i<=j
auto Cur = [&](int i, int j) { return 0<=min(i,j) && max(i,j)<n? cur[min(i,j)][max(i,j)] : -1; };

for (int L = 1; L <= 2*(n-1); L++, cur = next)
for (int i = max(L-n+1,0); i <= min(L,n-1); i++)
for (int j = i; j <= min(L,n-1); j++)
{   // max cherries for path length L-1 before arriving (i,k-1) and (j,k-j)
int curMax = max(max(Cur(i,j), Cur(i-1,j)), max(Cur(i,j-1),Cur(i-1,j-1)));
// max cherries for path length L reaching (i,k-1) and (j,k-j)
next[i][j] = (grid[i][L-i]>=0 && grid[j][L-j]>=0 && curMax>=0)? curMax+grid[i][L-i]+(i!=j)*grid[j][L-j] : -1;
}

return max(Cur(n-1,n-1), 0);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.