• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= A.length == A[0].length <= 100
  2. -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. 1 <= A.length == A[0].length <= 100
  2. -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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap