[Swift]LeetCode120.三角形最小路径和|Triangle

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

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

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

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

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

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

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

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

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

12ms

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

16ms

 1 class Solution {
 2     func minimumTotal(_ triangle: [[Int]]) -> Int {
 3         if triangle.count == 1 {
 4             return triangle[0][0]
 5         }
 6         var lastLine = triangle.last!
 7         var sums = Array(repeating: 0, count:triangle.count-1)
 8         for i in stride(from: triangle.count-2, through:0, by:-1) {
 9             for j in 0..<triangle[i].count {
10                 sums[j] = min(lastLine[j], lastLine[j+1]) + triangle[i][j]
11             }
12             lastLine = sums
13         }
14         return sums[0]
15     }
16 }

44ms

 1 class Solution {
 2     func minimumTotal(_ triangle: [[Int]]) -> Int {
 3         guard triangle.count > 0 else {
 4             return 0
 5         }
 6         
 7         var dp = triangle.last!
 8         
 9         for i in stride(from: triangle.count - 2, through: 0, by: -1) {
10             for j in 0...i {
11                 dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
12             }
13         }
14         
15         return dp[0]
16     }
17 }

96ms

 1 class Solution {
 2     
 3     func minimumTotal(_ triangle: [[Int]]) -> Int {
 4         let m = triangle.count
 5         if m == 0 { return 0 }
 6         if m == 1 { return triangle[0][0] }
 7         var result = triangle //设result[i][j]是到ij的最小路径和
 8         
 9         for i in 1 ..< m {
10             for j in 0 ... i {
11                 if j == 0 {
12                     result[i][j] = triangle[i][j] + result[i - 1][j]    
13                 } 
14                 else if j == i {
15                     result[i][j] = triangle[i][j] + result[i - 1][j - 1]    
16                 }
17                 else {
18                     result[i][j] = triangle[i][j] + min(result[i - 1][j], result[i - 1][j - 1])    
19                 }
20             }
21         }
22         
23         
24         return result[m - 1].min() ?? 0
25     }
26 }