[Swift]LeetCode64. 最小路径和 | Minimum Path Sum_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 an

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: 7Explanation: 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 = 011         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].count18         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] : 10050011         }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] = value15                 } 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     /// 二维数组序号转一维数组的Index29     private func indexFrom(_ y: Int,_ x: Int,_ grID: [[Int]]) -> Int {30         return y * grID.first!.count + x31     }32 }