# Annotated C++ DP Solution

• 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);
}
};
``````

• very nice solution!

• why do not

``````grid[i][k - i] < 0
``````

overflow when i = 0 && k > n?

• @张博文 yeah,so i put

``````if(k-i>=N||k-j>=N||grid[i][k-i]<0||grid[j][k-j]<0)continue;
``````

• Translate your code in Java and works perfectly.
Also, still wondering why would your original code work without checking y coordinate overflow, as somebody else pointed out. Did I miss anything?

``````class Solution {
public int cherryPickup(int[][] grid) {
int n = grid.length;
if (n == 0) return 0;
int[][] DP = new int[n][n];
for (int[] row : DP) Arrays.fill(row, -1);
int max_len = n*2 - 2; //max possible path length
DP[0][0] = grid[0][0];

//DP[i][j] in loop k: when the length of path is k,
//the x coord of path 1 is i, the x coord of path 2 is j,
//what's the max num of cherries?
for (int k = 1; k <= max_len; k++){
int[][] temp = new int[n][n];
for (int[] row : temp) Arrays.fill(row, -1);

for (int i = 0; i <= Math.min(k, n - 1); i++){
for (int j = 0; j <= Math.min(k, n - 1); j++){
if (k - i >= n || k - j >= n) continue; //y coord overflow
if (grid[i][k - i] == -1 || grid[j][k - j] == -1) continue;

int cur_cherry = DP[i][j];
if (i > 0) cur_cherry = Math.max(cur_cherry, DP[i - 1][j]);
if (j > 0) cur_cherry = Math.max(cur_cherry, DP[i][j - 1]);
if (i > 0 && j > 0) cur_cherry = Math.max(cur_cherry, DP[i - 1][j - 1]);
if (cur_cherry < 0) continue; //no possible way to here

if (i == j) temp[i][j] = cur_cherry + grid[i][k - i];
else temp[i][j] = cur_cherry + grid[i][k - i] + grid[j][k - j];
}
}
DP = temp;
}
return Math.max(0, DP[n - 1][n - 1]);
}
}
``````

• @张博文 I have the solution updated to take the "overflow" case into consideration.

As to why the program don't overflow when i = 0 && k > n, I think this is related to how C++ handles 2-D array in in memory.
In C++, 2-D array was stored continuously just like 1-D array.
So, suppose we have an array[3][3], the element array[2][3] is equivalent to array[3][0].

Example:

``````[story@StoryTeller:~]\$ cat hello.cpp
#include <cstdio>
int main() {
int arr[3][3] = {};
arr[2][3] = 5;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
printf("arr[%d][%d]=%d\n", i, j, arr[i][j]);
}
}
printf("%d\n", arr[2][3]);

printf("%d\n", arr[3][0]);
return 0;
}

[story@StoryTeller:~]\$ g++ hello.cpp -g
hello.cpp:4:5: warning: array index 3 is past the end of the array (which contains 3 elements)
[-Warray-bounds]
arr[2][3] = 5;
^      ~
hello.cpp:3:5: note: array 'arr' declared here
int arr[3][3] = {};
^
hello.cpp:10:20: warning: array index 3 is past the end of the array (which contains 3 elements)
[-Warray-bounds]
printf("%d\n", arr[2][3]);
^      ~
hello.cpp:3:5: note: array 'arr' declared here
int arr[3][3] = {};
^
2 warnings generated.
``````

• I very appreciate that you can give such detailed explanation
thanks a lot

• Nice, the DP takes some time to understand. I converted it to C# and needed to account for the array bounds (overflow). I will post that in C# and give some credit to you for idea, thanks.

• if (k - i >= n || k - j >= n) continue; //y coord overflow

Open Source versions of C++ allow that (there's lots of C++ solution on LeetCode not checking array/vector bounds). On the other hand, for Microsoft C++, you must explicitly turn off the checking with compiler options. If you were run the original in Visual Studio C++, it would also crash when k >= n;

• @dingess Also "hackers" love to go past the end of an array :-)

• @dingess Thanks for response. Yeah I rarely code in C++ so have totally no idea of this.

• This post is deleted!

• @storypku Great post. Due to symmetry,

for (int j = 0; j <= Math.min(k, n - 1); j++)
can be changed to
for (int j = i; j <= Math.min(k, n - 1); j++)

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