# C++ DP solution

• It is the same as two path start from (0, 0) to (n-1, n-1)
dp[x1][x2] means two length p path , currently one arrived at [..., x1] , the other is at [..., x2], the max value we can get

loop on length p, update max.

bottom to up, updated to use one n*n array.

``````class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int N = grid.size();
int P_LEN = N + N - 1;
vector<vector<int> > dp = vector<vector<int>>(N, vector<int>(N, -1));
dp[0][0] = grid[0][0];

for (int p = 2; p <= P_LEN; p++) {//p is the length of the path
for (int x1 = N - 1; x1 >= 0; x1--) {
for (int x2 = x1; x2 >= 0; x2--) {
int y1 = p - 1 - x1;
int y2 = p - 1 - x2;
if (y1 < 0 || y2 < 0 || y1 >= N || y2 >= N)
continue;
if (grid[y1][x1] < 0 || grid[y2][x2] < 0) {
dp[x1][x2] = -1;
continue;
}
int best = -1, delta = grid[y1][x1];
if (x1 != x2)
delta += grid[y2][x2];
if (x1 > 0 && x2 > 0 && dp[x1 - 1][x2 - 1] >= 0) //from left left
best = max(best, dp[x1 - 1][x2 - 1] + delta);
if (x1 > 0 && y2 > 0 && dp[x1 - 1][x2] >= 0) //from left up
best = max(best, dp[x1 - 1][x2] + delta);
if (y1 > 0 && x2 > 0 && dp[x1][x2 - 1] >= 0) //from up left
best = max(best, dp[x1][x2 - 1] + delta);
if (y1 > 0 && y2 > 0 && dp[x1][x2] >= 0) //from up up
best = max(best, dp[x1][x2] + delta);
dp[x1][x2] = best;
}
}
}
return dp[N - 1][N - 1] < 0 ? 0 : dp[N - 1][N - 1];
}
};
``````

• This is clever! Thanks!

One minor suggestion: we could easily remove the copy operation of "dp1 = dp2", by creating two references (or pointers) and flip their values at each iteration.

And looking at it more carefully, I think we could use only one dp matrix instead of two (dp1/dp2)?

• @Heart135 I guess you're referring to dp[x1][y1][x2][y2]. Then the space complexity will be O(n^4). While if using a flipper like p&1 and ~p&1, we can reducce the space complexity to O(n^2).

• @Victorcxq
(I might be too sleepy and talking nonsense at the moment. ;))
I thought we could use a single dp[x1][x2], but change the two for-loops for x1 and x2 to be decreasing. Does that make sense?

• Single DP Array

``````class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
dp[0][0] = grid[0][0];

for (int k = 1; k < 2 * n - 1; k++) {
vector<vector<int>> curr(n, vector<int>(n, -1));
for (int i = 0; i < n && i <= k; i++) {
for (int j = 0; j < n && j <= k; j++) {
if (grid[i][k - i] < 0 || grid[j][k - j] < 0) continue;

int t = dp[i][j];

if (i > 0) t = std::max(t, dp[i - 1][j]);
if (j > 0) t = std::max(t, dp[i][j - 1]);
if (i > 0 && j > 0) t = std::max(t, dp[i - 1][j - 1]);
if (t < 0) continue;
t += grid[i][k - i] + (i == j ? 0 : grid[j][k - j]);

curr[i][j] = t;
}
}

dp = std::move(curr);
}

return std::max(dp[n-1][n-1], 0);
}
};
``````

• @Heart135 I don't think so... Maybe you can write down your code to test it.
FYI, as you mentioned before, a modified version of this solution using a flipper as below:

``````class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int n = grid.size();
// for each path, it will end up with 2*n - 2
int plen = 2 * n - 2;
int dp[2][n][n];
// notice that we may use the same index in dp[p&1] and dp[~p&1]
// we need to initialize the matrix using -1 to avoid mistakes ((x1,x2) may not be reachable)
for (int i = 0; i<2; i++)
{
for (int j = 0; j<n; j++)
{
for (int k = 0; k<n; k++) dp[i][j][k] = -1;
}
}
dp[0][0][0] = grid[0][0];
dp[1][0][0] = grid[0][0];
// use a flipper: p&1 as p, ~p&1 as p-1
// loop over different length
for (int p = 1; p <= plen; p++)
{
for (int x1 = 0; x1 < n; x1++)
{
for (int x2 = x1; x2 < n; x2++)
{
int y1 = p - x1, y2 = p - x2;
if (y1 < 0 || y2 < 0 || y1 >= n || y2 >= n) continue;
if (grid[x1][y1] < 0 || grid[x2][y2] < 0)
{
dp[p&1][x1][x2] = -1;
continue;
}
int best = -1, delta = grid[x1][y1];
if (x1 != x2) delta += grid[x2][y2];
// (up, up), (up, left), (left, up), (left, left)
if (x1 > 0 && x2 > 0 && dp[~p&1][x1 - 1][x2 - 1] >= 0) best = max(best, dp[~p&1][x1 - 1][x2 - 1] + delta);
if (x1 > 0 && y2 > 0 && dp[~p&1][x1 - 1][  x2  ] >= 0) best = max(best, dp[~p&1][x1 - 1][  x2  ] + delta);
if (y1 > 0 && x2 > 0 && dp[~p&1][  x1  ][x2 - 1] >= 0) best = max(best, dp[~p&1][  x1  ][x2 - 1] + delta);
if (y1 > 0 && y2 > 0 && dp[~p&1][  x1  ][  x2  ] >= 0) best = max(best, dp[~p&1][  x1  ][  x2  ] + delta);
// update the value
dp[p&1][x1][x2] = best;
}
}
}
return dp[plen&1][n-1][n-1] < 0? 0 : dp[plen&1][n-1][n-1];
}
};
``````

@storypku you still use a curr[n][n]... I don't think it's a single version.
@jordandong Great solution! Thanks much for sharing it with us.

• @storypku The solution you posted still has to create a new matrix |curr| at each step.

The following solution eliminates that:

``````    int cherryPickup(vector<vector<int>>& grid) {
int d = grid.size();
int p_len = 2 * d - 1;

// state[x1][x2]: the max cherry number two paths of length p can collect.
// One path is <{0,0} ... {p - x1 - 1, x1}>; the other is
// <{0, 0} ... {p - x2 - 1, x2}>.
vector<vector<int>> state(d, vector<int>(d, -1));

state[0][0] = grid[0][0];

for (int p = 2; p <= p_len; ++p) {
for (int x1 = min(p,d) - 1; x1 >= 0; --x1) {
for (int x2 = min(p,d) - 1; x2 >= x1; --x2) {
int y1 = p - x1 - 1;
int y2 = p - x2 - 1;

if (y1 < 0 || y2 < 0 || y1 >= d || y2 >= d)
continue;

if (grid[y1][x1] == -1 || grid[y2][x2] == -1) {
state[x1][x2] = -1;
continue;
}

int gain = (x1 == x2) ? grid[y1][x1] : grid[y1][x1] + grid[y2][x2];

int value = -1;
if (x1 > 0 && state[x1-1][x2] >= 0) {
value = max(state[x1-1][x2] + gain, value);
}

if (x2 > 0 && state[x1][x2-1] >= 0) {
value = max(state[x1][x2-1] + gain, value);
}

if (x1 > 0 && x2 > 0 && state[x1-1][x2-1] >= 0) {
value = max(state[x1-1][x2-1] + gain, value);
}

if (state[x1][x2] >= 0) {
value = max(state[x1][x2] + gain, value);
}
state[x1][x2] = value;
}
}
}

return max(state[d-1][d-1], 0);
}
``````

• @Heart135 I see. You're right. Because dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1], if we carefully update the matrix from bottom right corner to top left corner, we will need only one matrix.

• hi
my understanding:
if we use 4-dimention, dp[x1][y1][x2][y2]

max(
dp[x1-1][y1][x2-1][y2] , (from left,left)
dp[x1][y1-1][x2][y2-1] , (from up, up)
dp[x1-1][y1][x2][y2-1] , (from left, up)
dp[x1][y1-2][x2-1][y2] , (from up, left)
) + grid[x1][y1] + grid[x2][y2]

in the code, why can dp1[x1-1][x2-1] represent left, left
seems reduce y axis? but how does it work?

thanks

• @reliveinfire the tricky part is due to the difference between matrix indices and coordinates. If you simply write an index for matrix grid, like grid[i][j], it means row i and column j. But row <--> y axis, column <--> x axis.

• @Victorcxq ok , but not pretty sure,
why dp1[x1-1][x2-1] can represent dp[x1-1][y1][x2-y][y2],

looks like rolling dp, reduce the y1/y2

• @reliveinfire given fixed length of path p, given x1, x2, we can calculate the corresponding y1 = p - x1 and y2 = p - x2. If y1 and y2 is not out of range, then both paths are legal paths. The key is to understand why we loop over different length of paths.

• @Victorcxq
thanks, i understand.
below is my understanding:

p is len of dp2
p' is len of dp1

for the loop, p' = p -1 (the loop difference is 1, dp1 is previous loop)
p = x1 + y1
dp2[x1], when p is constant, we can have y1 = p -x1

for dp1[x1]
y1' = p' - x1,
y1' = (p-1) - x1
y1' = y1 -1

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