# [741. Cherry Pickup] C++ DP and some comments

• Thanks for @storypku https://discuss.leetcode.com/topic/112877/annotated-c-dp-solution
and @jordandong
https://discuss.leetcode.com/topic/112856/c-dp-solution/2
who post their solutions.

At first I tried use DFS and separated the question into two parts: from [0,0] to [n-1,n-1] and from [n-1,n-1] to [0,0], but the time limit exceeded.

n is the side length of grid.

First of all, there are two phases, from [0,0] to [n-1,n-1] and from [n-1,n-1] to [0,0]. However, these two paths can be viewed both as from [0,0] to [n-1, n-1], because they are "mirror systematic". What we want is finding out the largest sum of two traverses both from [0,0] and [n-1, n-1].

Therefore, we use a 2D vector dp to store the largest sum of two paths. dp[i][j] is not so easy to understand, so here I explain i and j as:

• i: the going-down steps of the first path
• j: the going-down steps of the second path

We also know the total steps from [0,0] to [n-1,n-1] is 2n - 2. Suppose the current total steps for each of path are len, then
for i, the steps that it can go down is min(n-1, len); the same for the j.
Once we give the current total steps of each path, the final position in the grid of each path can be confirmed, which are grid[i][len - i] and grid[j][len - j]. Therefore, if grid[i][len - i] is -1 or grid[j][len - j] is -1, we can skip and continue to the i++ or j++ in our for loop.

Each time we increase our total steps by 1, and consider all possible paths in the two "mirror systematic" paths,

Basic idea is:
dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + grid[i][len-i] + grid[j][len-j]

Always remember that in the dp, dp[i][j] is the largest sum of two paths (the collected cherries), i and j is the steps of going-down for the two paths separately. In the grid[i][len-i] is the current position of path i in the grid, because the current total steps is len. The same for grid[j][len-j].

The following procedures can be checked in the code.

``````class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int n = grid.size();
if(n == 1) return grid[0][0];
int steps = 2*n - 2;

for(int len = 1; len <= steps; ++len){
vector<vector<int>> temp(n, vector<int>(n, -1));
for(int i = 0; i <= len && i < n; ++i){
for(int j = 0; j <= len && j < n; ++j){
if(grid[i][len -i] < 0 || grid[j][len - j] < 0) continue;
int cher = dp[i][j];

//three possible cases to reach current position in the two paths.
if(i > 0) cher = max(cher, dp[i-1][j]);
if(j > 0) cher = max(cher, dp[i][j-1]);
if(i > 0 && j > 0) cher = max(cher, dp[i-1][j-1]);

if(cher < 0) continue;
//if i and j are the same, it means i and j are in the same position in the grid.
cher += grid[i][len - i] + (i == j ? 0 : grid[j][len - j]);
temp[i][j] = cher;
}
}
dp = move(temp);
}
return max(dp[n-1][n-1], 0);
}
};``````

• Can you explain why need dp[i-1][j-1]? What I can understand is, dp[i-][j] and dp[i][j-1] are the largest number of cherries for len - 1 steps, but I do not understand why dp[i-1][j-1] also stands for len - 1 steps..

• @hpnhxxwn Actually we consider 4 cases:

dp[i][j]
dp[i-1][j]
dp[i][j-1]
dp[i-1][j-1]

the 4 directions which the two paths can reach to current positions. I revised the formula and added dp[i][j].

• Here is what I thought:
calculate dp[i][j] from dp[i][j-1] represents two paths that do not meet at the same place after moving one more step.
calculate dp[i][j] from dp[i-1][j-1] represents two paths that meet at the same place after moving one more step.

dp[i][j] itself is the result from past iteration of length 1 ~ len - 1, so we factor this in just because we want to pick the maximum.

Correct me if I'm wrong. Thank you.

• @hpnhxxwn I am not sure i understand your idea.
But i think it does not matter whether they meet at the same place or not.

As i stated:
i: the going-down steps of the first path
j: the going-down steps of the second path

So if we want the two paths at the status: first path going down for i steps, second path going down for j steps, we have 4 cases:

1. it is already at the status that we want, which is dp[i][j]

2. Previously, first path was at status "i-1" and then by going down 1 it becomes "i". Second path is already at status "j"

3. Previously, second path was at status "j-1" and then by going down 1 it becomes "j". First path is already at status "i"

4. Previously, first path was at status "i-1" and then by going down 1 it becomes "i". Second path was at status "j-1" and then by going down 1 it becomes "j".

And we keep updating dp[i][j] because we are extending our total steps.

The above analysis is my understanding, it might be wrong :-)
You can also check storypku's draft to help u understand this problem: https://discuss.leetcode.com/topic/112877/annotated-c-dp-solution

• @jasonshieh
i dont understand dp[i-1][j-1], neither.

is this supposed to be

max(
dp[i-1][j-1] + grid[i][len-i] + grid[j][len-j]
dp[i-1][j] + grid[i][len-i]
dp[i][j-1] + grid[j][len-j]
dp[i][j])
if the dp[i-1][j-1] is the previous status?
we add two new grid value for dp[i-1][j-1] (move i, move j)
but the original code, get the max, and add two steps?

thanks

• This post is deleted!

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