2020-02-03 17:46:04
问题描述：
问题求解：
非常好的题目，和two thumb其实非常类似，但是还是有个一点区别，就是本题要求最后要到达(n - 1, n - 1)，只有到达了(n - 1, n - 1)才算是有效解，two thumb是一定会有解的，所以不用加特别判断。
也是一种路径规划类的题目，难点依然是状态的表示，我们这里使用的p1，p2的坐标位置作为状态。
另外，还需要注意的是在超界的时候，我们需要返回的是Integer.MIN_VALUE，这样就可以规避掉一些中间节点到不了终点的情况。
int[][][] dp = new int[51][51][51];
public int cherryPickup(int[][] grid) {
int n = grid.length;
for (int i = 0; i <= 50; i++) {
for (int j = 0; j <= 50; j++) {
Arrays.fill(dp[i][j], -1);
}
}
int res = dfs(grid, 0, 0, 0);
return dp[n - 1][n - 1][n - 1] == -1 ? 0 : res;
}
private int dfs(int[][] grid, int x1, int y1, int x2) {
int n = grid.length;
int y2 = x1 + y1 - x2;
if (x1 >= n || y1 >= n || x2 >= n || y2 >= n) return Integer.MIN_VALUE;
if (dp[x1][y1][x2] != -1) return dp[x1][y1][x2];
else if (x1 == n - 1 && y1 == n - 1) dp[x1][y1][x2] = grid[n - 1][n - 1];
else if (grid[x1][y1] == -1 || grid[x2][y2] == -1) dp[x1][y1][x2] = Integer.MIN_VALUE;
else {
int curr = x1 == x2 && y1 == y2 ? grid[x1][y1] : grid[x1][y1] + grid[x2][y2];
dp[x1][y1][x2] = curr + Math.max(Math.max(dfs(grid, x1 + 1, y1, x2 + 1), dfs(grid, x1 + 1, y1, x2)), Math.max(dfs(grid, x1, y1 + 1, x2 + 1), dfs(grid, x1, y1 + 1, x2)));
}
return dp[x1][y1][x2];
}