05 August 2008
一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：
0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。
你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：
从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。
按照题意，一个人来回走两趟，必定在地图上留下两条路径。
我们可以想象有两个人，AA 和 BB，同时 从点 (0,0)(0,0) 出发。
每一次移动，两个人同时移动一步（向右或向下）。
容易证明，每次移动后，两个人必定在同一条对角线上。
如果某次移动后，两个人在同一位置，则最多只能摘得一个樱桃
最终，两个人都会移动到点 (N-1,N-1)(N−1,N−1) 上，留下两条路径。这两条路径所摘得樱桃数，即为题目所求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public int cherryPickup(int[][] grid) {
int len = grid.length;
int[][] dp = new int[len + 1][len + 1];
for (int[] row : dp) {
//使用了N+1的大小，因此边界值也设置为MIN_VALUE
Arrays.fill(row, Integer.MIN_VALUE);
}
//动态规划涉及方向，此题倒序来找
dp[len - 1][len - 1] = grid[len - 1][len - 1];
//sum表示一共要走的步数，也就是k，通过一个循环递增，来降低一个维度，从而不需要使用三维数组k那一维,
//当前走第sum步，一共要走2*len-2步（n-1）*2,下标的话就是2N-3，注意是倒序的
for (int sum = 2 * len - 3; sum >= 0; sum--) {
for (int i1 = Math.max(0, sum - len + 1); i1 <= Math.min(len - 1, sum); i1++) {
for (int i2 = i1; i2 <= Math.min(len - 1, sum); i2++) {
//i1、j2的关联：一共要走sum步，sum<2*n，因此起点为Math.max(0,sum-len+1),限定了i1的范围，因此 j1 = sum -i1 = sum - (sum-n+1) = n-1,也就是当i1取最大，j1的下标也只能为n-1
//i2的优化：从i1开始计算，表明第二个人一定走在i1的下面
int j1 = sum - i1;
int j2 = sum - i2;
if (grid[i1][j1] == -1 || grid[i2][j2] == -1) {
//遇到荆棘
dp[i1][i2] = Integer.MIN_VALUE;
} else {
if (i1 != i2 || j1 != j2) {
//不重合在同一个点，则获取的最大值=A的格子+B的格子+AB往哪个方向走，也就是上一个状态是怎么来得，
dp[i1][i2] = grid[i1][j1] + grid[i2][j2] + Math.max(Math.max(dp[i1][i2 + 1], dp[i1 + 1][i2]), Math.max(dp[i1][i2], dp[i1 + 1][i2 + 1]));
} else {
//重合在一个点，grid[i1][j1] == grid[i2][j2]，取一个即可，后面是4个方向
dp[i1][i2] = grid[i1][j1] + Math.max(Math.max(dp[i1][i2 + 1], dp[i1 + 1][i2]), Math.max(dp[i1][i2], dp[i1 + 1][i2 + 1]));
}
}
}
}
}
return Math.max(0, dp[0][0]);
}
}