问题
问题描述：给定一个方形整形数组A（行数 == 列数），计算出最小的下降路径之和。
下降路径可从第一行的任意一个元素开始，然后到下一行选择一个元素，要求下一行元素所在的列与上一行元素所在的列不能超过1，即只能在左边/右边/相同列。
栗子：
输入：[[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] 是最小之和路径。
注意：
1 <= A.length == A[0].length <= 100-100 <= A[i][j] <= 100
想看英文的戳这里：原题地址
解题思路
递归
这是一种很容易想到的方法，把所有可能的路径都遍历出来，计算最小和，但是由于 A.length <= 100，可能会导致递归次数过多。不过，还是先来尝试一下。
首先第一行，我们任意选取一个元素 i, sum = A[0][i]。
第二行，根据第一行选择的列，只可能选择j = i/ i-1/ i+1 其中一个，任意选定一个 sum += A[1][j]；
第三行，根据第二行选择的列，也只能选择 j = i/ i-1/ i+1 其中一个，任意选定一个 sum += A[1][j]；
第四行，重复以上步骤。
递归重复步骤：根据上一行选择元素所在的列，决定该行需要遍历哪些列，计算所选择的数之和为 sum，然后下一行再重复以上步骤。
递归结束条件：当最后一行遍历完成，即 row >= list.count，将 sum 与 全局的 minSum 做比较，这样递归完成后， minSum 就是最小的。
```
func recursive(_ row: Int, _ col: Int, _ sum: Int) {
if row < 0 || row >= list.count {
if sum < minSum {
minSum = sum
}
} else {
// 列相隔不超过1
var j = col - 1
while j <= col + 1 {
if j >= 0, j < c {
let tmp = sum + list[row][j]
recursive(row + 1, j, tmp)
}
j += 1
}
}
}
```
第一行的处理有点不一样，因为它可以遍历所有的元素，然后进行之后的递归。
var minSum = Int.max
var r = 0
var c = 0
var list = [[Int]]()
func minFallingPathSum(_ A: [[Int]]) -> Int {
r = A.count
if r > 0 {
list = A
c = A[0].count
var col = 0
// 遍历第一行
while col < c {
recursive(1, col, A[0][col])
col += 1
}
}
return minSum
}
验证进行提交后，发现结果是 Time Limited Exceeded，超时，递归耗费的时间太长了，失败的 case 是 20 * 20 的数组。
每个元素下一行可选的元素最多为 3，因为最左/最右的只能选择 2 个。
以 2 来粗略估算一下最小值：
n = 20
row-1：选择一个数 1 次，但需要重复 n 次；
row-2：执行 2 次；
row-3：执行 2 * 2 次；
row-4：执行 2 * 2 * 2 次；
...
row-n：执行 2 ^(n - 1) 次；
以上加起来：(1 + 2 + 2^2 + 2 ^ 3 + 2 ^(n - 1)) * n
minCount = 20 * (2^20 - 1) = 20971500，千万级别。
以 3 估算最大值：
maxCount = 20 * (3^20 - 1) = 697,3568,8000，百亿级别。
看起来次数量级还是挺大的，而 n 还可能取到 100，量级会更大，时间更多。
动态规划
递归中其实有很多都是重复的计算。如果将已经遍历过的数的最小和存起来，那么下次就可以直接取，省去重新计算的过程。
举个栗子，有如下数组 A ：
[
[1,2,3],
[4,5,6],
[7,8,9]
]
-
如果第一行取
2，第二行可能取4，5，6；如果从4，5，6开始的最小路径之和已经计算好，那么从2开始的路径最小和为path(2) = 2 + min(path(4), path(5), path(6))；那么
path(4)要怎么求呢？很简单，只需要根据其下一行来计算，而下一行是最后一行了，可直接计算：path(4) = min(4 + 7, 4 + 8)。path(5)的求法同上。 -
如果第一行取
3，第二行可能取5，6；如果从5,6开始的最小路径之和已经计算好，那么path(3) = 3 + min(path(5), path(6))path(5)其实已经求过了，直接取即可。
最终思想：求出每个位置的最小路径之和，只需要一层层往下推，最终会落地到先求最后一层的最小值之和（为原值），然后是倒数第二层，倒数第三层 ... 第一层。
最后，
第一层中的最小值，就是最小路径之和。
最终公式如下：
path(r, c) = A[r][c] + min(path(r+1, c - 1), path(r+1, c), path(r+1, c + 1))
swift 代码如下：
func minFallingPathSum_2(_ A: [[Int]]) -> Int {
// 采用从底向上计算的方式，计算出每个位置的最小和，一步步往上计算，到第一层时，就已经计算出了所有的最小和，只需要遍历第一行最小的数即可。
r = A.count
if r > 0 {
list = A
c = A[0].count
var tmp = A
// 从倒数第二行开始计算，因为倒数第一行各个位置的最小和肯定是原值。
if r >= 2 {
var i = r - 2
while i >= 0 {
var j = 0
// 计算每个位置最小和
while j < c {
// 最小和
var minSum = Int.max
// 当前位置的数
let n = tmp[i][j]
// 从其左边一列起
var k = j - 1
// 遍历起相邻列，不超过1
while k <= j + 1 {
if k >= 0, k < c {
// 加上它下一行的数
let sum = n + tmp[i+1][k]
if sum < minSum {
minSum = sum
}
}
k += 1
}
// 记录最小和
tmp[i][j] = minSum
j += 1
}
i -= 1
}
}
// 找到第一行中的最小值
let firstRow = tmp[0]
var minSum = Int.max
for n in firstRow {
if n < minSum {
minSum = n
}
}
return minSum
}
return 0
}
完整代码：https://github.com/silan-liu/Leetcode/tree/master/minFallingPathSum
网友评论