[Swift Weekly Contest 108]LeetCode931. 下降路径最小和 | Minimum Falling Path Sum

概述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 c

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,8],9] [2,[2,9],6,9] [3,[3,9]

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

 Note:

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

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

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

示例：

输入：[[1,9]]输出：12解释：可能的下降路径有：

[1,9]

和最小的下降路径是 [1,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..<m10             {11                 for k in -1...112                 {13                     if i+k >= 0 && i+k < m14                     {15                         ndp[i + k] = min(ndp[i + k],dp[i] + A[j + 1][i + k])16                     }17                 }18             }19             dp = ndp20         }21         var ret:Int = Int.max22         for v in dp23         {24             ret = min(ret,v)25         }26         return ret27     }28 }

总结

以上是内存溢出为你收集整理的[Swift Weekly Contest 108]LeetCode931. 下降路径最小和 | Minimum Falling Path Sum全部内容，希望文章能够帮你解决[Swift Weekly Contest 108]LeetCode931. 下降路径最小和 | Minimum Falling Path Sum所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。