741. 摘樱桃
一个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) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。示例 1:
输入: grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]] 输出: 5 解释： 玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。 在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。 接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。 在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。说明:
grid 是一个 N * N 的二维数组，N的取值范围是1 <= N <= 50。每一个 grid[i][j] 都是集合 {-1, 0, 1}其中的一个数。可以保证起点 grid[0][0] 和终点 grid[N-1][N-1] 的值都不会是 -1。version 01___DFS遍历__未完成
public class Solution { /** * 此题名为摘樱桃;这个不好摘啊，思路呢 先写个贪心算法试试看咯 所以此题为贪心算法版本 * * @param grid * @return */ public int cherryPickup(int[][] grid) { //dfsGo和dfsBack只需要实现1个即可，另一个同理推知 return dfsGo(grid, 0, 0) + dfsBack(grid, grid.length - 1, grid.length - 1); } //写到这里写不下去了，似乎是进行了遍历，也能找到最大的值， //但是不知道如何去记录走过的路径，日后有能力了希望能解决此困难。 int dfsGo(int[][] grid, int row, int column) { // 踩到刺啦 if (grid[row][column] == -1) return -1; // 走到边儿啦 if (row == grid.length - 1 || column == grid.length - 1) { if (row == grid.length - 1 && column == grid.length - 1) return grid[row][column]; else if (column == grid.length - 1) { return dfsGo(grid, row + 1, column);} else return dfsGo(grid, row, column + 1); } // 贪心吃最大 int ds=dfsGo(grid,row+1,column);//ds___down step int rs=dfsGo(grid,row,column+1);//rs___right step if (ds>=rs&&ds==-1) return -1;//两边都是刺，堵死了 if(ds>=rs) { return ds+grid[row][column]; } else { return rs+grid[row][column]; } } }version2___动态规划__测试不通过
version2遇到的测试案例：内心很绝望。。。
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
public class Solution2 { /** * 此篇为摘樱桃的动态规划版本，突然想起以前学过的课，似乎可以用动态规划来解决问题。 * 走过去的时候，对任一结点grid[row][column],走到grid[row][column]点获得的樱桃 * nums[row][column]=max(nums[row-1][column],nums[row][column-1])+grid[row][column] * 所以可以提前遍历整个二维数组，建立好nums数组。 * * @param grid * @return */ public int cherryPickup(int[][] grid) { // dfsGo和dfsBack只需要实现1个即可，另一个同理推知 int go = go(grid); int back = back(grid); return (go + back)>0?go+back:0; } int go(int[][] grid) { // 创建nums数组然后遍历获取最大值。 int[][] nums = new int[grid.length][grid.length]; getNums(nums, grid); //清除走过的路径。 clearPath(nums, grid); return nums[grid.length - 1][grid.length - 1]; } void getNums(int[][] nums, int[][] grid) { for (int i = 0; i < grid.length; i++) for (int j = 0; j < grid.length; j++) { // 刺伤不能走 if (grid[i][j] == -1) nums[i][j] = -1; else if (i > 0 && j > 0) { if (nums[i - 1][j] == -1 && nums[i][j - 1] == -1) nums[i][j] = -1; else nums[i][j] = grid[i][j] + (nums[i - 1][j] >= nums[i][j - 1] ? nums[i - 1][j] : nums[i][j - 1]); } else if (i == 0 && j > 0) { if (nums[i][j - 1] == -1) nums[i][j] = -1; else nums[i][j] = grid[i][j] + nums[i][j - 1]; } else if (j == 0 && i > 0) { if (nums[i - 1][j] == -1) nums[i][j] = -1; else nums[i][j] = grid[i][j] + nums[i - 1][j]; } else nums[0][0] = grid[0][0]; } } void clearPath(int[][] nums, int[][] grid) { for (int i = grid.length - 1, j = grid.length-1;;) { grid[i][j] = 0; if (i > 0 && j > 0) if (nums[i - 1][j] >= nums[i][j - 1]) i--; else j--; else if (i == 0 && j > 0) j--; else if (j == 0 && i > 0) i--; else break; } } int back(int[][] grid) { // 创建nums数组然后遍历获取最大值。 int[][] numsback = new int[grid.length][grid.length]; getNumsBack(numsback, grid); return numsback[0][0]; } void getNumsBack(int[][] nums, int[][] grid) { for (int i = grid.length-1; i>=0; i--) for (int j = grid.length-1; j >=0; j--) { // 刺伤不能走 if (grid[i][j] == -1) nums[i][j] = -1; else if (i < grid.length-1 && j < grid.length-1) { if (nums[i + 1][j] == -1 && nums[i][j + 1] == -1) nums[i][j] = -1; else nums[i][j] = grid[i][j] + (nums[i + 1][j] >= nums[i][j + 1] ? nums[i + 1][j] : nums[i][j + 1]); } else if (i == grid.length-1 && j != grid.length-1) { if (nums[i][j + 1] == -1) nums[i][j] = -1; else nums[i][j] = grid[i][j] + nums[i][j + 1]; } else if (j == grid.length-1 && i != grid.length-1) { if (nums[i + 1][j] == -1) nums[i][j] = -1; else nums[i][j] = grid[i][j] + nums[i + 1][j]; } else nums[grid.length-1][grid.length-1] = grid[grid.length-1][grid.length-1]; } }至此，贪心算法无发完成目标。。。。