[Swift]LeetCode64.最小路径和|MinimumPathSum

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9922166.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

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

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

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,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, x, 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 }