★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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:
gridis anNbyN2D array, with1 <= 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.
一个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。
384ms
1 class Solution { 2 func cherryPickup(_ grid: [[Int]]) -> Int { 3 let n = grid.count 4 var dp = Array(repeating: Array(repeating: Array(repeating: -1, count: n+1), count: n+1), count: n+1) 5 6 dp[1][1][1] = grid[0][0] 7 for x1 in 1...n { 8 for y1 in 1...n { 9 for x2 in 1...n {10 let y2 = x1 + y1 - x2;11 if dp[x1][y1][x2] > 0 ||12 y2 < 1 || 13 y2 > n || 14 grid[x1 - 1][y1 - 1] == -1 || 15 grid[x2 - 1][y2 - 1] == -1 {16 continue17 }18 let cur = max(max(dp[x1 - 1][y1][x2], dp[x1 - 1][y1][x2 - 1]), 19 max(dp[x1][y1 - 1][x2], dp[x1][y1 - 1][x2 - 1]))20 if cur < 0 {21 continue22 }23 dp[x1][y1][x2] = cur + grid[x1 - 1][y1 - 1]24 if x1 != x2 {25 dp[x1][y1][x2] += grid[x2 - 1][y2 - 1]26 }27 }28 }29 }30 return dp[n][n][n] < 0 ? 0 : dp[n][n][n]31 }32 } 740ms
1 class Solution { 2 func cherryPickup(_ grid: [[Int]]) -> Int { 3 let length = grid.count 4 guard length != 0 && length == grid.first!.count && length >= 1 && length <= 50 && grid[0][0] != -1 && grid[length - 1][length - 1] != -1 else { 5 return 0 6 } 7 var pickUpCount = Array(repeating: Array(repeating: -1, count: length), count: length) 8 pickUpCount[0][0] = grid[0][0] 9 if length > 1 {10 for step in 1 ... (length - 1) * 2 {11 let xMax = min(length - 1, step), xMin = max(0, step - (length - 1))12 for x1 in stride(from: xMax, through: xMin, by: -1) {13 for x2 in stride(from: xMax, through: xMin, by: -1) {14 let y1 = step - x1, y2 = step - x215 if grid[x1][y1] == -1 || grid[x2][y2] == -1 {16 pickUpCount[x1][x2] = -117 continue18 }19 if y1 > 0 && x2 > 0 {20 pickUpCount[x1][x2] = max(pickUpCount[x1][x2], pickUpCount[x1][x2 - 1])21 }22 if x1 > 0 && y2 > 0 {23 pickUpCount[x1][x2] = max(pickUpCount[x1][x2], pickUpCount[x1 - 1][x2])24 }25 if x1 > 0 && x2 > 0 {26 pickUpCount[x1][x2] = max(pickUpCount[x1][x2], pickUpCount[x1 - 1][x2 - 1])27 }28 if pickUpCount[x1][x2] == -1 {29 continue30 }31 if x1 == x2 {32 pickUpCount[x1][x2] += grid[x1][y1]33 } else {34 pickUpCount[x1][x2] += grid[x1][y1] + grid[x2][y2]35 }36 }37 }38 }39 }40 return max(pickUpCount[length - 1][length - 1], 0)41 }42 } Runtime: 876 ms
Memory Usage: 19 MB
1 class Solution { 2 func cherryPickup(_ grid: [[Int]]) -> Int { 3 var n:Int = grid.count 4 var mx:Int = 2 * n - 1 5 var dp:[[Int]] = [[Int]](repeating:[Int](repeating:-1,count:n),count:n) 6 dp[0][0] = grid[0][0] 7 for k in 1.. = n || q < 0 || q >= n || grid[i][j] < 0 || grid[p][q] < 016 {17 dp[i][p] = -118 continue19 }20 if i > 0 {dp[i][p] = max(dp[i][p], dp[i - 1][p])}21 if p > 0 {dp[i][p] = max(dp[i][p], dp[i][p - 1])}22 if i > 0 && p > 0 {dp[i][p] = max(dp[i][p], dp[i - 1][p - 1])}23 if dp[i][p] >= 0 {dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0)}24 }25 }26 }27 return max(dp[n - 1][n - 1], 0)28 }29 }