https://leetcode.com/problems/cherry-pickup/description/
0 means the cell is empty, so you can pass through;
1 means the cell contains a cherry, that you can pick up and pass through;
-1 means the cell contains a thorn that blocks your way.
Starting at the position (0, 0) and reaching (N-1, N-1) by moving right or down through valid path cells (cells with value 0 or 1);
After reaching (N-1, N-1), returning to (0, 0) by moving left or up through valid path cells;
When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0);
If there is no valid path between (0, 0) and (N-1, N-1), then no cherries can be collected.
Each
It is guaranteed that grid[0][0] and grid[N-1][N-1] are not -1.
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-741-cherry-pickup/
https://leetcode.com/problems/cherry-pickup/discuss/109903/Step-by-step-guidance-of-the-O(N3)-time-and-O(N2)-space-solution
Instead of walking from end to beginning, let's reverse the second leg of the path, so we are only considering two paths from the beginning to the end.
X. DP
https://segmentfault.com/a/1190000017557146
X. DP - time
https://leetcode.com/problems/cherry-pickup/discuss/109903/step-by-step-guidance-of-the-on3-time-and-on2-space-solution
那么首先，我们想到的肯定是一个贪心的思路，先找正向一条最优的路，把路过的1变0，再重新dp一遍
这个思路是错误的，我自己验证的方法是先假设这个贪心正确，再用反证法尝试证明，在证明过程中，你就会发现一些无法cover的情况，比如一条最大权路径收益为6，两条次大收益路径相互没有重叠，收益为5，而最大路径分别和这两个次大路径重叠了2，假如其它位置都是0，那么贪心方法收益最大是9，而选两个次大路径收益是10
那么我们就需要重新设计dp状态，把重叠这个问题考虑进去
首先我们知道，正反两次走，等价于分别做两次正着走。问题就变成分别走两次找最大收益，其中第一次走过的1会变成0。
然后我们进一步，简化理解，可以是2个人同时正着走，且速度一样，希望两人总体的收益最大，如果它们同时走到一个格子上，那它们只能拿一次。可以简单理解一下为什么这个问题，和刚才的问题等价：设速度都是1，则第t个时刻，设第一个人走到(x1, y1)，第二个人走到(x2, y2)，那么一定有x1 + y1 = t，x2 + y2 = t，假如x1 != x2，那么这一次行程中，第一个人永远不会走到(x2, y2)，同理第二人永远不会走到(x1, y1)。因此，拿重的问题只会在它们同时走到一个格子的时候遇到，因此我们判断他们每个时刻是否会到达同一个格子就可以去重了。
把这个思想转换成dp的状态，则可以表示为dp(t, x1, x2)，也就是第t时刻第一个人走到(x1, t - x1)，第二个人走到(x2, t - x2)时两人的最大收益。
状态转移也非常简单：dp(t, x1, x2) = grid(x1, t - x1) + (x1 == x2 ? 0 : grid(x2, t - x2)) + max(dp(t-1, x1, x2), dp(t - 1, x1, x2 - 1), dp(t - 1, x1 - 1, x2), dp(t - 1, x1 - 1, x2 - 1))
最后就是t这一维我们可以通过滚动数组压掉，注意这样的话需要反向遍历更新dp
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 < (n << 1) - 1; k++){
for (int i = min(n - 1, k); i >= 0 && i >= k - n + 1; i--){
for (int j = min(n - 1, k); j >= 0 && j >= k - n + 1; j--){
int p = k - i, q = k - j;
if (grid[i][p] == -1 || grid[j][q] == -1){
dp[i][j] = -1;
continue;
}
if (p > 0 && j > 0){
dp[i][j] = max(dp[i][j], dp[i][j-1]);
}
if (i > 0){
if (j > 0)
dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
if (q > 0)
dp[i][j] = max(dp[i][j], dp[i-1][j]);
}
if (dp[i][j] == -1)
continue;
if (i == j)
dp[i][j] += grid[i][p];
else
dp[i][j] += grid[i][p] + grid[j][q];
}
}
}
return max(dp[n-1][n-1], 0);
}
X. https://leetcode.com/articles/cherry-pickup/
Approach #1: Greedy [Wrong Answer]
In a N x N
grid representing a field of cherries, each cell is one of three possible integers.
Your task is to collect maximum number of cherries possible by following the rules below:
Example 1:
Input: grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]] Output: 5 Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2). 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]]. Then, the player went left, up, up, left to return home, picking up one more cherry. The total number of cherries picked up is 5, and this is the maximum possible.
Note:
grid is an N by N 2D array, with 1 <= N <= 50.grid[i][j] is an integer in the set {-1, 0, 1}.https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-741-cherry-pickup/
Key observation: (0,0) to (n-1, n-1) to (0, 0) is the same as (n-1,n-1) to (0,0) twice
- Two people starting from (n-1, n-1) and go to (0, 0).
- They move one step (left or up) at a time simultaneously. And pick up the cherry within the grid (if there is one).
- if they ended up at the same grid with a cherry. Only one of them can pick up it.
Solution: DP / Recursion with memoization.
x1, y1, x2 to represent a state y2 can be computed: y2 = x1 + y1 – x2
dp(x1, y1, x2) computes the max cherries if start from {(x1, y1), (x2, y2)} to (0, 0), which is a recursive function.
Since two people move independently, there are 4 subproblems: (left, left), (left, up), (up, left), (left, up). Finally, we have:
dp(x1, y1, x2)= g[y1][x1] + g[y2][x2] + max{dp(x1-1,y1,x2-1), dp(x1,y1-1,x2-1), dp(x1-1,y1,x2), dp(x1,y1-1,x2)}
Time complexity: O(n^3)
Space complexity: O(n^3)
I -- A naive idea towards the solution
To begin with, you may be surprised by the basic ideas to approach the problem: simply simulate each of the round trips and choose the one that yields the maximum number of cherries.
But then what's the difficulty of this problem? The biggest issue is that there are simply too many round trips to explore -- the number of round trips scales exponentially as the size
N of the grid. This is because each round trip takes (4N-4) steps, and at each step, we have two options as to where to go next (in the worst case). This puts the total number of possible round trips at 2^(4N-4). Therefore a naive implementation of the aforementioned idea would be very inefficient.II -- Initial attempt of DP
Fortunately, a quick look at the problem seems to reveal the two features of dynamic programming: optimal substructure and overlapping of subproblems.
Optimal substructure: if we define
T(i, j) as the maximum number of cherries we can pick up starting from the position (i, j)(assume it's not a thorn) of the grid and following the path (i, j) ==> (N-1, N-1) ==>(0, 0), we could move one step forward to either (i+1, j) or (i, j+1), and recursively solve for the subproblems starting from each of those two positions (that is, T(i+1, j) and T(i, j+1)), then take the sum of the larger one (assume it exists) together with grid[i][j] to form a solution to the original problem. (Note: the previous analyses assume we are on the first leg of the round trip, that is, (0, 0) ==> (N-1, N-1); if we are on the second leg, that is, (N-1, N-1) ==> (0, 0), then we should move one step backward from (i, j) to either (i-1, j) or (i, j-1).)
Overlapping of subproblems: two round trips may overlap with each other in the middle, leading to repeated subproblems. For example, the position
(i, j) can be reached from both positions (i-1, j) and (i, j-1), which means both T(i-1, j) and T(i, j-1) are related to T(i, j). Therefore we may cache the intermediate results to avoid recomputing these subproblems.
This sounds promising, since there are at most
O(N^2) starting positions, meaning we could solve the problem in O(N^2) time with caching. But there is an issue with this naive DP -- it failed to take into account the constraint that "once a cherry is picked up, the original cell (value 1) becomes an empty cell (value 0)", so that if there are overlapping cells between the two legs of the round trip, those cells will be counted twice. In fact, without this constraint, we can simply solve for the maximum number of cherries of the two legs of the round trip separately (they should have the same value), then take the sum of the two to produce the answer.
The idea is based on the observation that the problem is equal to the maximal # of combined cherries picked by two persons starting simultaneously from point (n-1, n-1) towards point (0, 0)
dp[x1][y1][x2]: Given path 1 from (x1, y1) to (0, 0) and path 2 from (x2, x1+y1-x2) to (0, 0), the max picked cherries combined.
public int cherryPickup(int[][] grid) {
if (grid==null || grid.length==0 || grid[0].length==0) return 0;
int n=grid.length;
int[][][] dp=new int[n+1][n+1][n+1];
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++)
Arrays.fill(dp[i][j], -1);
dp[1][1][1]=grid[0][0];
for (int x1=1;x1<=n;x1++){
for (int y1=1;y1<=n;y1++){
for (int x2=1;x2<=n;x2++){
int y2=x1+y1-x2;
if (dp[x1][y1][x2]>=0 || y2<1 || y2>n || grid[x1-1][y1-1]<0 || grid[x2-1][y2-1]<0) continue;
int max1=Math.max(dp[x1-1][y1][x2], dp[x1][y1-1][x2]);
int max2=Math.max(dp[x1-1][y1][x2-1], dp[x1][y1-1][x2-1]);
int max=Math.max(max1, max2);
if (max==-1) continue;
dp[x1][y1][x2]=max+grid[x1-1][y1-1];
if (x2!=x1) dp[x1][y1][x2] += grid[x2-1][y2-1];
}
}
}
return Math.max(0, dp[n][n][n]);
}Instead of walking from end to beginning, let's reverse the second leg of the path, so we are only considering two paths from the beginning to the end.
Notice after
t steps, each position (r, c) we could be, is on the line r + c = t. So if we have two people at positions (r1, c1) and (r2, c2), then r2 = r1 + c1 - c2. That means the variables r1, c1, c2uniquely determine 2 people who have walked the same r1 + c1 number of steps. This sets us up for dynamic programming quite nicely.
Algorithm
Let
dp[r1][c1][c2] be the most number of cherries obtained by two people starting at (r1, c1) and (r2, c2) and walking towards (N-1, N-1) picking up cherries, where r2 = r1+c1-c2.
If
grid[r1][c1] and grid[r2][c2] are not thorns, then the value of dp[r1][c1][c2] is (grid[r1][c1] + grid[r2][c2]), plus the maximum of dp[r1+1][c1][c2], dp[r1][c1+1][c2], dp[r1+1][c1][c2+1], dp[r1][c1+1][c2+1] as appropriate. We should also be careful to not double count in case (r1, c1) == (r2, c2).
Why did we say it was the maximum of
dp[r+1][c1][c2] etc.? It corresponds to the 4 possibilities for person 1 and 2 moving down and right:- Person 1 down and person 2 down:
dp[r1+1][c1][c2]; - Person 1 right and person 2 down:
dp[r1][c1+1][c2]; - Person 1 down and person 2 right:
dp[r1+1][c1][c2+1]; - Person 1 right and person 2 right:
dp[r1][c1+1][c2+1];
- Time Complexity: , where is the length of
grid. Our dynamic programming has states. - Space Complexity: , the size of
memo.
int[][][] memo;
int[][] grid;
int N;
public int cherryPickup(int[][] grid) {
this.grid = grid;
N = grid.length;
memo = new int[N][N][N];
for (int[][] layer : memo)
for (int[] row : layer)
Arrays.fill(row, Integer.MIN_VALUE);
return Math.max(0, dp(0, 0, 0));
}
public int dp(int r1, int c1, int c2) {
int r2 = r1 + c1 - c2;
if (N == r1 || N == r2 || N == c1 || N == c2 || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
return -999999;
} else if (r1 == N - 1 && c1 == N - 1) {
return grid[r1][c1];
} else if (memo[r1][c1][c2] != Integer.MIN_VALUE) {
return memo[r1][c1][c2];
} else {
int ans = grid[r1][c1];
if (c1 != c2)
ans += grid[r2][c2];
ans += Math.max(Math.max(dp(r1, c1 + 1, c2 + 1), dp(r1 + 1, c1, c2 + 1)),
Math.max(dp(r1, c1 + 1, c2), dp(r1 + 1, c1, c2)));
memo[r1][c1][c2] = ans;
return ans;
}
}
https://raw.githubusercontent.com/cherryljr/LeetCode/master/Cherry%20Pickup.java public int cherryPickup(int[][] grid) {
int n = grid.length;
mem = new int[n][n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
mem[i][j][k] = Integer.MIN_VALUE;
}
}
}
return Math.max(0, dfs(grid, n - 1, n - 1, n - 1));
}
private int dfs(int[][] grid, int x1, int y1, int x2) {
int y2 = x1 + y1 - x2;
// 当前方案行不通，这返回 -1.（包括处理边界条件）
if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0 || grid[x1][y1] == -1 || grid[x2][y2] == -1) {
return -1;
}
// 到达结束位置（左上角），递归结束
if (x1 == 0 && y1 == 0) {
return grid[0][0];
}
// 当前状态已经计算过，则直接返回
if (mem[x1][y1][x2] != Integer.MIN_VALUE) {
return mem[x1][y1][x2];
}
// 递归调用四个子过程（每个人有两种走法，有两个人，所以总共 2*2 = 4 个子状态）
int rst = Math.max(Math.max(dfs(grid, x1 - 1, y1, x2), dfs(grid, x1 - 1, y1, x2 - 1)),
Math.max(dfs(grid, x1, y1 - 1, x2), dfs(grid, x1, y1 - 1, x2 - 1)));
// 所有的子过程都行不通，则返回 -1.
if (rst < 0) {
mem[x1][y1][x2] = -1;
return rst;
}
// 拾取(x1, y1)当前位置的樱桃
rst += grid[x1][y1];
// 如果两个人的位置不同，则也需要拾取(x2, y2)位置的樱桃。
if (x1 != x2) {
rst += grid[x2][y2];
}
mem[x1][y1][x2] = rst;
return mem[x1][y1][x2];
}
https://segmentfault.com/a/1190000017557146
public int cherryPickup(int[][] grid) {
int n = grid.length;
int[][][] dp = new int[n+1][n+1][n+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
Arrays.fill(dp[i][j], Integer.MIN_VALUE);
}
}
dp[1][1][1] = grid[0][0];
for (int x1 = 1; x1 <= n; x1++) {
for (int y1 = 1; y1 <= n; y1++) {
for (int x2 = 1; x2 <= n; x2++) {
int y2 = x1+y1-x2;
if (dp[x1][y1][x2] > 0 ||
y2 < 1 || y2 > n ||
grid[x1-1][y1-1] == -1 || grid[x2-1][y2-1] == -1) continue;
int preMax = Math.max(
Math.max(dp[x1-1][y1][x2], dp[x1-1][y1][x2-1]),
Math.max(dp[x1][y1-1][x2], dp[x1][y1-1][x2-1])
);
if (preMax < 0) continue;
dp[x1][y1][x2] = preMax + grid[x1-1][y1-1];
if (x1 != x2) dp[x1][y1][x2] += grid[x2-1][y2-1];
}
}
}
return dp[n][n][n] < 0 ? 0 : dp[n][n][n];
}
Say
r1 + c1 = t is the t-th layer. Since our recursion only references the next layer, we only need to keep two layers in memory at a time.
Algorithm
At time
t, let dp[c1][c2] be the most cherries that we can pick up for two people going from (0, 0) to (r1, c1) and (0, 0) to (r2, c2), where r1 = t-c1, r2 = t-c2. Our dynamic program proceeds similarly to Approach #2.
public int cherryPickup(int[][] grid) {
int N = grid.length;
int[][] dp = new int[N][N];
for (int[] row : dp)
Arrays.fill(row, Integer.MIN_VALUE);
dp[0][0] = grid[0][0];
for (int t = 1; t <= 2 * N - 2; ++t) {
int[][] dp2 = new int[N][N];
for (int[] row : dp2)
Arrays.fill(row, Integer.MIN_VALUE);
for (int i = Math.max(0, t - (N - 1)); i <= Math.min(N - 1, t); ++i) {
for (int j = Math.max(0, t - (N - 1)); j <= Math.min(N - 1, t); ++j) {
if (grid[i][t - i] == -1 || grid[j][t - j] == -1)
continue;
int val = grid[i][t - i];
if (i != j)
val += grid[j][t - j];
for (int pi = i - 1; pi <= i; ++pi)
for (int pj = j - 1; pj <= j; ++pj)
if (pi >= 0 && pj >= 0)
dp2[i][j] = Math.max(dp2[i][j], dp[pi][pj] + val);
}
}
dp = dp2;
}
return Math.max(0, dp[N - 1][N - 1]);
}
https://leetcode.com/problems/cherry-pickup/discuss/109903/step-by-step-guidance-of-the-on3-time-and-on2-space-solution
T(i, j, p, q) = grid[i][j] + grid[p][q] + max{T(i-1, j, p-1, q), T(i-1, j, p, q-1), T(i, j-1, p-1, q), T(i, j-1, p, q-1)}public int cherryPickup(int[][] grid) {
int N = grid.length, M = (N << 1) - 1;
int[][] dp = new int[N][N];
dp[0][0] = grid[0][0];
for (int n = 1; n < M; n++) {
for (int i = N - 1; i >= 0; i--) {
for (int p = N - 1; p >= 0; p--) {
int j = n - i, q = n - p;
if (j < 0 || j >= N || q < 0 || q >= N || grid[i][j] < 0 || grid[p][q] < 0) {
dp[i][p] = -1;
continue;
}
if (i > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p]);
if (p > 0) dp[i][p] = Math.max(dp[i][p], dp[i][p - 1]);
if (i > 0 && p > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p - 1]);
if (dp[i][p] >= 0) dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0)
}
}
}
return Math.max(dp[N - 1][N - 1], 0);
}
这道题给了我们一个二维数组，每个数字只有三个数字，-1，0，和1，其中-1表示障碍物不能通过，1表示有樱桃并可以通过，0表示没有樱桃并可以通过，并设定左上角为起点，右下角为终点，让我们从起点走到终点，再从终点返回起点，求最多能捡的樱桃的个数，限定起点和终点都没有障碍物。博主开始想的是就用dp来做呗，先从起点走到终点，求最多能捡多个樱桃，然后将捡起樱桃后将grid值变为0，然后再走一遍，把两次得到的樱桃数相加即可，但是类似贪婪算法的dp解法却跪在了下面这个case：
1 1 1 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 1 1 1
我们可以看出，红色的轨迹是第一次dp解法走过的路径，共拿到了13个樱桃，但是回到起点的话，剩下的两个樱桃无论如何也不可能同时拿到，只能拿到1颗，所以总共只能捡到14颗樱桃，而实际上所有的樱桃都可以捡到，需要换个走法的话，比如下面这种走法：
1 1 1 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 1 1 1
红色为从起点到终点的走法，共拿到9颗樱桃，回去走蓝色的路径，可拿到6颗樱桃，所以总共15颗都能收入囊中。那这是怎么回事，原因出在了我们的dp递推式的设计上，博主之前设计式，当前位置的樱桃数跟上边和左边的樱桃数有关，取二者的较大值，如果只是从起点到终点走单程的话，这种设计是没有问题的，可以拿到最多的樱桃，但如果是round trip的话，那么就不行了。这里参考的还是fun4LeetCode大神的帖子，范佛利特扣德大神的帖子每次讲解都写的巨详细，总是让博主有种读paper的感觉。博主就挑选部分来讲讲，完整版可以自己去读一读大神的亲笔～
最开始时博主定义的dp[i][j]为单程的，即到达(i, j)位置能捡到的最大樱桃数，即：
T(i, j) = grid[i][j] + max{ T(i-1, j), T(i, j-1) }
但是定义单程就得改变grid的值，再进行一次dp计算时，就会陷入之前例子中的陷阱。所以我们的dp[i][j]还是需要定义为round trip的，即到达(i, j)位置并返回起点时能捡到的最大樱桃数，但是新的问题就来了，樱桃只有一个，只能捡一次，去程捡了，返程就不能再捡了，如何才能避免重复计算呢？我们只有i和j是不够的，其只能定义去程的位置，我们还需要pg，(不是pgone哈哈)，来定义返程的位置，那么重现关系Recurrence Relations就变成了 T(i, j, p, g)，我们有分别两种方式离开(i, j)和(p, g)，我们suppose时从终点往起点遍历，那么就有4种情况：
Case 1: (0, 0) ==> (i-1, j) ==> (i, j); (p, q) ==> (p-1, q) ==> (0, 0) Case 2: (0, 0) ==> (i-1, j) ==> (i, j); (p, q) ==> (p, q-1) ==> (0, 0) Case 3: (0, 0) ==> (i, j-1) ==> (i, j); (p, q) ==> (p-1, q) ==> (0, 0) Case 4: (0, 0) ==> (i, j-1) ==> (i, j); (p, q) ==> (p, q-1) ==> (0, 0)
根据定义，我们有：
Case 1 is equivalent to T(i-1, j, p-1, q) + grid[i][j] + grid[p][q]; Case 2 is equivalent to T(i-1, j, p, q-1) + grid[i][j] + grid[p][q]; Case 3 is equivalent to T(i, j-1, p-1, q) + grid[i][j] + grid[p][q]; Case 4 is equivalent to T(i, j-1, p, q-1) + grid[i][j] + grid[p][q];
因此，我们的重现关系可以写作：
T(i, j, p, q) = grid[i][j] + grid[p][q] + max{T(i-1, j, p-1, q), T(i-1, j, p, q-1), T(i, j-1, p-1, q), T(i, j-1, p, q-1)}
为了避免重复计算，我们希望 grid[i][j] 和 grid[p][g] 不出现在T(i-1, j, p-1, q), T(i-1, j, p, q-1), T(i, j-1, p-1, q) 和 T(i, j-1, p, q-1)中的任意一个上。显而易见的是(i, j)不会出现在(0, 0) ==> (i-1, j) 或 (0, 0) ==> (i, j-1) 的路径上，同理，(p, g) 也不会出现在 (p-1, q) ==> (0, 0) 或 (p, q-1) ==> (0, 0) 的路径上。因此，我们需要保证(i, j) 不会出现在 (p-1, q) ==> (0, 0) 或 (p, q-1) ==> (0, 0) 的路径上，同时 (p, g)不会出现在(0, 0) ==> (i-1, j) 或 (0, 0) ==> (i, j-1) 的路径上，怎么做呢？
我们观察到(0, 0) ==> (i-1, j) 和 (0, 0) ==> (i, j-1) 的所有点都在矩形 [0, 0, i, j] 中（除了右下角点(i, j)点），所以只要 (p, g) 不在矩形 [0, 0, i, j] 中就行了，注意(p, g) 和 (i, j) 是有可能重合了，这种情况特殊处理一下就行了。同理， (i, j) 也不能在矩形 [0, 0, p, g] 中，那么以下三个条件中需要满足一个：
i < p && j > q i == p && j == q i > p && j < q
为了满足上述条件，我们希望当 i 或 p 增加的时候，j 或 q 减小，那么我们可以有这个等式:
k = i + j = p + q
其中k为从起点开始走的步数，所以我们可以用 T(k, i, p) 来代替 T(i, j, p, g)，那么我们的重现关系式就变成了：
T(k, i, p) = grid[i][k-i] + grid[p][k-p] + max{T(k-1, i-1, p-1), T(k-1, i-1, p), T(k-1, i, p-1), T(k-1, i, p)}.
当 i == p 时，grid[i][k-i] 和 grid[p][k-p] 就相等了，此时只能加一个。我们注意到 i, j, p, q 的范围是 [0, n)， 意味着k只能在范围 [0, 2n - 1) 中， 初始化时 T(0, 0, 0) = grid[0][0]。我们这里的重现关系T虽然是三维的，但是我们可以用二维dp数组来实现，因为第k步的值只依赖于第k-1步的情况
int cherryPickup(vector<vector<int>>& grid) { int n = grid.size(), mx = 2 * n - 1; vector<vector<int>> dp(n, vector<int>(n, -1)); dp[0][0] = grid[0][0]; for (int k = 1; k < mx; ++k) { for (int i = n - 1; i >= 0; --i) { for (int p = n - 1; p >= 0; --p) { int j = k - i, q = k - p; if (j < 0 || j >= n || q < 0 || q >= n || grid[i][j] < 0 || grid[p][q] < 0) { dp[i][p] = -1; continue; } if (i > 0) dp[i][p] = max(dp[i][p], dp[i - 1][p]); if (p > 0) dp[i][p] = max(dp[i][p], dp[i][p - 1]); if (i > 0 && p > 0) dp[i][p] = max(dp[i][p], dp[i - 1][p - 1]); if (dp[i][p] >= 0) dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0); } } } return max(dp[n - 1][n - 1], 0); }https://blog.csdn.net/luke2834/article/details/79365645
那么首先，我们想到的肯定是一个贪心的思路，先找正向一条最优的路，把路过的1变0，再重新dp一遍
这个思路是错误的，我自己验证的方法是先假设这个贪心正确，再用反证法尝试证明，在证明过程中，你就会发现一些无法cover的情况，比如一条最大权路径收益为6，两条次大收益路径相互没有重叠，收益为5，而最大路径分别和这两个次大路径重叠了2，假如其它位置都是0，那么贪心方法收益最大是9，而选两个次大路径收益是10
那么我们就需要重新设计dp状态，把重叠这个问题考虑进去
首先我们知道，正反两次走，等价于分别做两次正着走。问题就变成分别走两次找最大收益，其中第一次走过的1会变成0。
然后我们进一步，简化理解，可以是2个人同时正着走，且速度一样，希望两人总体的收益最大，如果它们同时走到一个格子上，那它们只能拿一次。可以简单理解一下为什么这个问题，和刚才的问题等价：设速度都是1，则第t个时刻，设第一个人走到(x1, y1)，第二个人走到(x2, y2)，那么一定有x1 + y1 = t，x2 + y2 = t，假如x1 != x2，那么这一次行程中，第一个人永远不会走到(x2, y2)，同理第二人永远不会走到(x1, y1)。因此，拿重的问题只会在它们同时走到一个格子的时候遇到，因此我们判断他们每个时刻是否会到达同一个格子就可以去重了。
把这个思想转换成dp的状态，则可以表示为dp(t, x1, x2)，也就是第t时刻第一个人走到(x1, t - x1)，第二个人走到(x2, t - x2)时两人的最大收益。
状态转移也非常简单：dp(t, x1, x2) = grid(x1, t - x1) + (x1 == x2 ? 0 : grid(x2, t - x2)) + max(dp(t-1, x1, x2), dp(t - 1, x1, x2 - 1), dp(t - 1, x1 - 1, x2), dp(t - 1, x1 - 1, x2 - 1))
最后就是t这一维我们可以通过滚动数组压掉，注意这样的话需要反向遍历更新dp
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 < (n << 1) - 1; k++){
for (int i = min(n - 1, k); i >= 0 && i >= k - n + 1; i--){
for (int j = min(n - 1, k); j >= 0 && j >= k - n + 1; j--){
int p = k - i, q = k - j;
if (grid[i][p] == -1 || grid[j][q] == -1){
dp[i][j] = -1;
continue;
}
if (p > 0 && j > 0){
dp[i][j] = max(dp[i][j], dp[i][j-1]);
}
if (i > 0){
if (j > 0)
dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
if (q > 0)
dp[i][j] = max(dp[i][j], dp[i-1][j]);
}
if (dp[i][j] == -1)
continue;
if (i == j)
dp[i][j] += grid[i][p];
else
dp[i][j] += grid[i][p] + grid[j][q];
}
}
}
return max(dp[n-1][n-1], 0);
}
X. https://leetcode.com/articles/cherry-pickup/
Approach #1: Greedy [Wrong Answer]
Intuition
Let's find the most cherries we can pick up with one path, pick them up, then find the most cherries we can pick up with a second path on the remaining field.
Though a counter example might be hard to think of, this approach fails to find the best answer to this case:
11100 00101 10100 00100 00111
