[Swift]LeetCode64. 最小路径和 | Minimum Path Sum

发布时间：2020-12-14 05:10:12 所属栏目：百科来源：网络整理

导读：Given a? m ?x? n ?grid filled with non-negative numbers,find a path from top left to bottom right which? minimizes ?the sum of all numbers along its path. Note:?You can only move either down or right at any point in time. Example: Input:[?

Given a?m?x?n?grid filled with non-negative numbers,find a path from top left to bottom right which?minimizes?the sum of all numbers along its path.

Note:?You can only move either down or right at any point in time.

Example:

Input:
[
? [1,3,1],[1,5,[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

给定一个包含非负整数的?m?x?n?网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
? [1,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

20ms

 1 class Solution {
 2     func minPathSum(_ grid: [[Int]]) -> Int {
 3         guard grid.count > 0 else {
 4             return 0
 5         }
 6         let m = grid.count
 7         let n = grid[0].count
 8         var dp = Array(repeating:0,count: n)
 9         dp[0] = grid[0][0]
10         for i in 1..<n {
11             dp[i] = dp[i - 1] + grid[0][i]
12         }
13         for i in 1..<m {
14             for j in 0..<n {
15                 if j == 0 {
16                     dp[j] += grid[i][0]
17                 } else {
18                     dp[j] = min(dp[j],dp[j - 1]) + grid[i][j]
19                 }
20             }
21         }
22         return dp[n - 1]
23     }
24 }

24ms

 1 class Solution {
 2     func minPathSum(_ grid: [[Int]]) -> Int {
 3         guard grid.count>0 else { return 0}
 4         var rows = grid.count
 5         var cols = grid[0].count
 6         var dp = Array(repeating:Array(repeating:0,count:cols),count:rows)
 7         
 8         
 9         dp[0][0] = grid[0][0]
10         var row = 0,col = 0
11         for row in 1..<rows {
12             dp[row][0] = dp[row-1][0] + grid[row][0]
13         }
14         
15         for col in 1..<cols {
16             dp[0][col] = dp[0][col-1] + grid[0][col]
17         }
18         
19         for row in 1..<rows {
20             for col in 1..<cols {
21                 dp[row][col] = min(dp[row-1][col],dp[row][col-1]) + grid[row][col]
22             }
23         }
24         
25         
26         return dp[rows-1][cols-1]
27         
28     }
29 }

24ms

 1 class Solution {
 2     func minPathSum(_ grid: [[Int]]) -> Int {
 3         guard grid.count > 0 else {
 4             return 0
 5         }
 6         var row = [Int].init(repeating: 0,count: grid[0].count+1)
 7         for i in 1..<row.count {
 8             row[i] = row[i-1] + grid[0][i-1]
 9         }
10         
11         for i in 1..<grid.count {
12             row[1] = row[1] + grid[i][0]
13             for j in 1..<grid[0].count {
14                 row[j+1] = row[j] > row[j+1] ? row[j+1] + grid[i][j] : row[j] + grid[i][j]
15             }
16         }
17         let resultIndex = grid[0].count
18         return row[resultIndex]
19     }
20 }

28ms

 1 class Solution {
 2     func minPathSum(_ grid: [[Int]]) -> Int {
 3         var grid = grid
 4         let m = grid.count
 5         let n = grid.first!.count
 6         func top(_ row: Int,_ column: Int) -> Int {
 7             return row-1 >= 0 ? grid[row-1][column] : 100500
 8         }
 9         func left(_ row: Int,_ column: Int) -> Int {
10             return column-1 >= 0 ? grid[row][column-1] : 100500
11         }
12         for row in 0..<m {
13             for column in 0..<n {
14                 if row == 0 && column == 0 { continue }
15                 grid[row][column] += min(top(row,column),left(row,column))
16             }
17         }
18         return grid.last!.last!
19     }
20 }

44ms

 1 class Solution {
 2     func minPathSum(_ grid: [[Int]]) -> Int { 
 3         var rows = Array.init(repeating: 0,count: grid[0].count)
 4         var result = Array.init(repeating: rows,count: grid.count)
 5         
 6         result[0][0] = grid[0][0]
 7         
 8         for i in 1..<grid.count {
 9             result[i][0] = grid[i][0] + result[i - 1][0]
10         }
11         
12         for i in 1..<grid[0].count {
13             result[0][i] = grid[0][i] + result[0][i - 1]
14         }
15         
16         for row in 1..<grid.count {
17             for col in 1..<grid[row].count {
18                 let a = result[row - 1][col]
19                 let b = result[row][col - 1]
20                 
21                 result[row][col] = min(a,b) + grid[row][col]
22             }
23         }
24      
25         return result[grid.count - 1][grid[0].count - 1]
26     }
27     
28     func res(_ row:Int,_ col: Int,_ grid:[[Int]]) -> Int {
29         if row == 0 && col == 0 {
30             return grid[0][0]
31         } else if row == 0 {
32             return res(0,col - 1,grid) + grid[row][col]
33         } else if col == 0{
34             return res(row - 1,0,grid) + grid[row][col]
35         } else {
36             let a = res(row - 1,col,grid);
37             let b = res(row,col - 1,grid); 
38             return min(a,b) + grid[row][col]
39         }
40     }
41 }

?48ms

 1 class Solution {
 2     func minPathSum(_ grid: [[Int]]) -> Int {
 3         var grid = grid
 4         let n = grid.count
 5         let m = grid[0].count
 6         
 7         for i in 1..<n {
 8             grid[i][0] += grid[i-1][0]
 9         }
10         
11         for j in 1..<m {
12             grid[0][j] += grid[0][j-1]
13         }
14         
15         for i in 1..<n {
16             for j in 1..<m {
17                 grid[i][j] += min(grid[i-1][j],grid[i][j-1])
18             }
19         }
20         
21         for i in 0..<n {
22             for j in 0..<m {
23                 print(grid[i][j],terminator: " ")
24             }
25             print()
26         }
27         
28         return grid[n-1][m-1]
29     }
30 }

56ms

 1 class Solution {
 2     func minPathSum(_ grid: [[Int]]) -> Int {
 3         if grid.count == 0 || grid.first!.count == 0 {
 4             return 0
 5         }
 6         var memo: [Int] = Array(repeating: 0,count: grid.count * grid.first!.count)
 7         for y in 0..<grid.count {
 8             for x in 0..<grid.first!.count {
 9                 let value = grid[y][x]
10                 let index = indexFrom(y,x,grid)
11                 let topIndex = indexFrom(y - 1,grid)
12                 let leftIndex = indexFrom(y,x - 1,grid)
13                 if x == 0 && y == 0 {
14                     memo[index] = value
15                 } else if x == 0 { // 第一列,仅由其上方位置值决定
16                     memo[index] = value + memo[topIndex]
17                 } else if y == 0 { // 第一行,同理
18                     memo[index] = value + memo[leftIndex]
19                 } else {
20                     memo[index] = min(value + memo[leftIndex],value + memo[topIndex])
21                 }
22             }
23         }
24         
25         return memo.last!
26     }
27     
28     /// 二维数组序号转一维数组的Index
29     private func indexFrom(_ y: Int,_ x: Int,_ grid: [[Int]]) -> Int {
30         return y * grid.first!.count + x
31     }
32 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!