741. Cherry Pickup

In a N x N grid representing a field of cherries, each cell is one of three possible integers.

 

• 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.

Your task is to collect maximum number of cherries possible by following the rules below:

• 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.

 

Example 1:

Input: grid =[[0, 1, -1], [1, 0, -1], [1, 1,  1]]Output: 5Explanation: 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.
• Each grid[i][j] is an integer in the set {-1, 0, 1}.
• It is guaranteed that grid[0][0] and grid[N-1][N-1] are not -1.
•  

解法：看起来和2d的Max path sum很像，所以想到也是DP的解法。但是不能用(0, 0) -> (n-1, n-1) (n-1, n-1) -> (0, 0) 两次DP：像，所以想

因为这个例子，最优解可以是从0，0走黄色到n,n，回头走粉色，可以得到所有1。

1110000101101000010000111 如果用两次DP的方法的 从0，0走黄色到n,n，回头走最后一列粉色，无论如何会漏掉一个1，所以不是最优。

1110000101101000010000111

所以我们需要同时有两个点的横纵坐标放入dp function。

题意说的是头到尾 moving right or down，从尾到头 moving left or up，但是算的时候可以用两个点同时从同个位置出发，便于计算。比如说 两个点 x, y 横纵坐标为(x1,x2) (y1,y2) ，同时从(n-1,n-1)出发，move moving left or up. 如果grid 长度为4：

(x1,x2) = {3,3}  (y1, y2) = {3, 3} 

next positions: 

{3,2} {3,2}  (x left, y left)

{2,3} {2,3}  (x up, y up)

{3,2} {2,3}  (x left, y up)

{2,3} {3,2}  (x up, y left)

注意到

x1 + x2 = y1 + y2 =>  y2 = x1 + x2 - y2, 所以 dp中可以用三个参数就好，减少计算量。

注意的点：

题意说如果没有路线要返回-1，所以如果越界或grid值为-1， return -1。但是注意要在(0,0)(0,0) init，如果没有init，(0,0)(0,0)的邻居都越界返回-1，所有值就都会变成-1。

 

1 public int cherryPickup(int[][] grid) { 2         HashMap
     
       hm = new HashMap
      
       (); 3         hm.put("0:0:0", grid[0][0]); // init 4         return Math.max(0, helper(hm, grid.length - 1, grid[0].length - 1, grid.length - 1, grid)); 5  6     } 7  8     int[][] delta = new int[][]{
   {0, -1, 0}, {-1, 0, -1}, {-1, 0, 0}, {0, -1, -1}}; 9     private int helper(HashMap
       
         hm, int x1, int x2, int y1, int[][] grid) {10         if (hm.containsKey(x1 + ":" + x2 + ":" + y1)) {11             return hm.get(x1 + ":" + x2 + ":" + y1);12         }13         int y2 = x1 + x2 - y1;14 15         if (x1 < 0 || x1 >= grid.length || x2 < 0 || x2 >= grid[0].length || y1 < 0 || y1 >= grid.length16             || y2 < 0 || y2 >= grid[0].length || grid[x1][x2] == -1 || grid[y1][y2] == -1) {17             return -1;18         }19         int cur = 0;20         if (x1 == y1 && x2 == y2) {21             if (grid[x1][x2] == 1) {22                 cur += 1;23             }24         } else { 25             if (grid[x1][x2] == 1) {26                 cur += 1;27             }28             if (grid[y1][y2] == 1) {29                 cur += 1;30             }31         }32         int neighbor = Integer.MIN_VALUE;33         for (int k = 0; k < delta.length; k++) {34             neighbor = Math.max(neighbor, helper(hm, x1 + delta[k][0], x2 + delta[k][1], y1 + delta[k][2], grid));35         }36         if (neighbor < 0) {37             hm.put(x1 + ":" + x2 + ":" + y1, -1);38             return -1;39         }40         hm.put(x1 + ":" + x2 + ":" + y1, neighbor + cur);41         return neighbor + cur;42     }