★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： http://www.noobyard.com/article/p-kbmgbcfh-me.html
➤若是连接不是山青咏芝的博客园地址，则多是爬取做者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持做者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★html
In a N x N grid representing a field of cherries, each cell is one of three possible integers.git
Your task is to collect maximum number of cherries possible by following the rules below:github
Example 1:数组
Input: grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]] Output: 5 Explanation: 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.grid[i][j] is an integer in the set {-1, 0, 1}.一个N x N的网格(grid) 表明了一块樱桃地，每一个格子由如下三种数字的一种来表示：ide
你的任务是在遵照下列规则的状况下，尽量的摘到最多樱桃：this
示例 1:spa
输入: 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颗樱桃，这是能够摘到的最大值了。
说明:code
grid 是一个 N * N 的二维数组，N的取值范围是1 <= N <= 50。grid[i][j] 都是集合 {-1, 0, 1}其中的一个数。grid[0][0] 和终点 grid[N-1][N-1] 的值都不会是 -1。384mshtm
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 continue 17 } 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 continue 22 } 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 - x2 15 if grid[x1][y1] == -1 || grid[x2][y2] == -1 { 16 pickUpCount[x1][x2] = -1 17 continue 18 } 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 continue 30 } 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 }
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..<mx 8 { 9 for i in stride(from:n - 1,through:0,by:-1) 10 { 11 for p in stride(from:n - 1,through:0,by:-1) 12 { 13 var j:Int = k - i 14 var q:Int = k - p 15 if j < 0 || j >= n || q < 0 || q >= n || grid[i][j] < 0 || grid[p][q] < 0 16 { 17 dp[i][p] = -1 18 continue 19 } 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 }