[Swift]LeetCode931.下降路径最小和|MinimumFallingPathSum

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

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

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

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

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

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

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:

[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.

Note:

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

示例：

输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：

[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

和最小的下降路径是 [1,4,7]，所以答案是 12。

提示：

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

196ms

 1 class Solution {
 2     func minFallingPathSum(_ A: [[Int]]) -> Int {
 3         let m:Int = A[0].count
 4         var dp:[Int] = A[0]
 5         for j in 0..<(A.count - 1)
 6         {
 7             var row:[Int] = A[j]
 8             var ndp:[Int] = [Int](repeating: Int.max / 2,count: m)
 9             for i in 0..<m
10             {
11                 for k in -1...1
12                 {
13                     if i+k >= 0 && i+k < m
14                     {
15                         ndp[i + k] = min(ndp[i + k], dp[i] + A[j + 1][i + k])
16                     }
17                 }
18             }
19             dp = ndp
20         }
21         var ret:Int = Int.max
22         for v in dp
23         {
24             ret = min(ret, v)
25         }
26         return ret
27     }
28 }

100ms

 1 class Solution {
 2     func minFallingPathSum(_ A: [[Int]]) -> Int {
 3         var currentRow = A[0]
 4         
 5         for i in 1..<A.count {
 6             var nextRow = [Int]()
 7             let r = A[i]
 8             for j in 0..<r.count {
 9                 var v = currentRow[j]
10                 if j > 0 {
11                     v = min(v, currentRow[j-1])
12                 }
13                 if j+1 < r.count {
14                     v = min(v, currentRow[j+1])
15                 }
16                 nextRow.append(r[j] + v)
17             }
18             currentRow = nextRow
19         }
20         let result = currentRow.reduce(Int.max){min($0, $1)}
21         return result
22     }
23 }

104ms

 1 class Solution {
 2     func minFallingPathSum(_ A: [[Int]]) -> Int {
 3         var dp: [Int] = A[0]
 4         for i in 1 ..< A.count {
 5             var pre = Int.max
 6             for j in 0 ..< A[i].count {
 7                 var cost = 0
 8                 if j == 0 {
 9                     cost = min(dp[j], dp[j + 1])
10                 } else if j == A.count - 1 {
11                     cost = min(pre, dp[j])
12                 } else {
13                     cost = min(min(pre, dp[j]), dp[j + 1])
14                 }
15                 pre = dp[j]
16                 dp[j] = A[i][j] + cost
17             }
18         }
19         var minCost = Int.max
20         for cost in dp {
21             minCost = min(minCost, cost)
22         }
23         return minCost
24     }
25 }

108ms

 1 class Solution {
 2     func minFallingPathSum(_ A: [[Int]]) -> Int {
 3        var dp = A[0]
 4         let count = A[0].count
 5         for i in 1..<A.count{
 6             var tempDp = [Int](repeating: Int.max, count: count)
 7             for j in 0..<count{
 8                 for k in max(j-1, 0)...min(j+1, count-1){
 9                     tempDp[j] = min(tempDp[j], dp[k])
10                 }
11                 tempDp[j] += A[i][j]
12             }
13             dp = tempDp
14         }
15         return dp.min()!
16     }
17 }

120ms

 1 class Solution {
 2     func minFallingPathSum(_ A: [[Int]]) -> Int {
 3         guard A.count > 1 else { return minRow(A[0])}
 4         var mutA = A
 5         var rowNum = 1
 6         while rowNum < mutA.count {
 7             defer { rowNum += 1 }
 8             for i in (0..<mutA[rowNum].count) {
 9                 let el = mutA[rowNum][i]
10                 mutA[rowNum][i] = el + mutA[rowNum-1][i]
11                 if i-1 >= 0 {
12                     mutA[rowNum][i] = min(mutA[rowNum][i], el + mutA[rowNum-1][i-1])
13                 }
14                 if i+1 < mutA[rowNum].count {
15                     mutA[rowNum][i] = min(mutA[rowNum][i], el + mutA[rowNum-1][i+1])
16                 }
17             }
18         }
19         return minRow(mutA[rowNum-1])
20     }
21     
22     func minRow(_ A: [Int]) -> Int {
23         var minEl = Int.max
24         for a in A {
25             if a < minEl {
26                 minEl = a
27             }
28         }
29         return minEl
30     }
31 }