It takes me quite some time to understand the DP solution to this problem this afternoon.

So I post the solution here with annotations for anyone who might find helpful.

**Updated Dec 05, 2017.** Thanks for @张博文 @xu8908 @szyyn95 for pointing out the overflow case.

```
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int n = grid.size();
// dp holds maximum # of cherries two k-length paths can pickup.
// The two k-length paths arrive at (i, k - i) and (j, k - j),
// respectively.
vector<vector<int>> dp(n, vector<int>(n, -1));
dp[0][0] = grid[0][0]; // length k = 0
// maxK: number of steps from (0, 0) to (n-1, n-1).
const int maxK = 2 * (n - 1);
for (int k = 1; k <= maxK; k++) { // for every length k
vector<vector<int>> curr(n, vector<int>(n, -1));
// one path of length k arrive at (i, k - i)
for (int i = 0; i < n && i <= k; i++) {
if ( k - i >= n) continue;
// another path of length k arrive at (j, k - j)
for (int j = 0; j < n && j <= k; j++) {
if (k - j >= n) continue;
if (grid[i][k - i] < 0 || grid[j][k - j] < 0) { // keep away from thorns
continue;
}
int cherries = dp[i][j]; // # of cherries picked up by the two (k-1)-length paths.
// See the figure below for an intuitive understanding
if (i > 0) cherries = std::max(cherries, dp[i - 1][j]);
if (j > 0) cherries = std::max(cherries, dp[i][j - 1]);
if (i > 0 && j > 0) cherries = std::max(cherries, dp[i - 1][j - 1]);
// No viable way to arrive at (i, k - i)-(j, k-j).
if (cherries < 0) continue;
// Pickup cherries at (i, k - i) and (j, k -j ) if i != j.
// Otherwise, pickup (i, k-i).
cherries += grid[i][k - i] + (i == j ? 0 : grid[j][k - j]);
curr[i][j] = cherries;
}
}
dp = std::move(curr);
}
return std::max(dp[n-1][n-1], 0);
}
};
```