問(wèn)題
問(wèn)題描述：給定一個(gè)方形整形數(shù)組A（行數(shù) == 列數(shù)）乌昔，計(jì)算出最小的下降路徑之和欢瞪。
下降路徑可從第一行的任意一個(gè)元素開(kāi)始，然后到下一行選擇一個(gè)元素，要求下一行元素所在的列與上一行元素所在的列不能超過(guò)1汉买，即只能在左邊/右邊/相同列。
栗子：
輸入：[[1,2,3], [4,5,6], [7,8,9]]
輸出：12
可能出現(xiàn)的路徑如下：
[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
想看英文的戳這里：原題地址
解題思路
遞歸
這是一種很容易想到的方法陕赃，把所有可能的路徑都遍歷出來(lái)，計(jì)算最小和瓜挽，但是由于 A.length <= 100盹廷，可能會(huì)導(dǎo)致遞歸次數(shù)過(guò)多。不過(guò)久橙，還是先來(lái)嘗試一下俄占。
首先第一行，我們?nèi)我膺x取一個(gè)元素 i, sum = A[0][i]淆衷。
第二行缸榄，根據(jù)第一行選擇的列，只可能選擇j = i/ i-1/ i+1 其中一個(gè)祝拯，任意選定一個(gè) sum += A[1][j]甚带；
第三行，根據(jù)第二行選擇的列佳头，也只能選擇 j = i/ i-1/ i+1 其中一個(gè)鹰贵，任意選定一個(gè) sum += A[1][j]；
第四行畜晰，重復(fù)以上步驟砾莱。
遞歸重復(fù)步驟：根據(jù)上一行選擇元素所在的列，決定該行需要遍歷哪些列凄鼻，計(jì)算所選擇的數(shù)之和為 sum腊瑟，然后下一行再重復(fù)以上步驟。
遞歸結(jié)束條件：當(dāng)最后一行遍歷完成块蚌，即 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 {
// 列相隔不超過(guò)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
}
}
}
```
第一行的處理有點(diǎn)不一樣，因?yàn)樗梢员闅v所有的元素，然后進(jìn)行之后的遞歸辆毡。
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
}
驗(yàn)證進(jìn)行提交后菜秦，發(fā)現(xiàn)結(jié)果是 Time Limited Exceeded，超時(shí)舶掖，遞歸耗費(fèi)的時(shí)間太長(zhǎng)了球昨，失敗的 case 是 20 * 20 的數(shù)組。
每個(gè)元素下一行可選的元素最多為 3眨攘，因?yàn)樽钭?最右的只能選擇 2 個(gè)主慰。
以 2 來(lái)粗略估算一下最小值：
n = 20
row-1：選擇一個(gè)數(shù) 1 次，但需要重復(fù) n 次鲫售；
row-2：執(zhí)行 2 次共螺；
row-3：執(zhí)行 2 * 2 次；
row-4：執(zhí)行 2 * 2 * 2 次情竹；
...
row-n：執(zhí)行 2 ^(n - 1) 次藐不；
以上加起來(lái)：(1 + 2 + 2^2 + 2 ^ 3 + 2 ^(n - 1)) * n
minCount = 20 * (2^20 - 1) = 20971500，千萬(wàn)級(jí)別秦效。
以 3 估算最大值：
maxCount = 20 * (3^20 - 1) = 697,3568,8000佳吞，百億級(jí)別。
看起來(lái)次數(shù)量級(jí)還是挺大的棉安，而 n 還可能取到 100，量級(jí)會(huì)更大铸抑，時(shí)間更多贡耽。
動(dòng)態(tài)規(guī)劃
遞歸中其實(shí)有很多都是重復(fù)的計(jì)算。如果將已經(jīng)遍歷過(guò)的數(shù)的最小和存起來(lái)鹊汛，那么下次就可以直接取蒲赂，省去重新計(jì)算的過(guò)程。
舉個(gè)栗子刁憋，有如下數(shù)組 A ：
[
[1,2,3],
[4,5,6],
[7,8,9]
]
-
如果第一行取
2滥嘴，第二行可能取4，5至耻，6若皱；如果從4，5尘颓，6開(kāi)始的最小路徑之和已經(jīng)計(jì)算好走触，那么從2開(kāi)始的路徑最小和為path(2) = 2 + min(path(4), path(5), path(6))；那么
path(4)要怎么求呢疤苹？很簡(jiǎn)單互广，只需要根據(jù)其下一行來(lái)計(jì)算，而下一行是最后一行了，可直接計(jì)算：path(4) = min(4 + 7, 4 + 8)惫皱。path(5)的求法同上像樊。 -
如果第一行取
3，第二行可能取5旅敷，6生棍；如果從5,6開(kāi)始的最小路徑之和已經(jīng)計(jì)算好，那么path(3) = 3 + min(path(5), path(6))path(5)其實(shí)已經(jīng)求過(guò)了扫皱，直接取即可足绅。
最終思想：求出每個(gè)位置的最小路徑之和，只需要一層層往下推韩脑，最終會(huì)落地到先求最后一層的最小值之和（為原值）氢妈，然后是倒數(shù)第二層，倒數(shù)第三層 ... 第一層段多。
最后首量，
第一層中的最小值，就是最小路徑之和进苍。
最終公式如下：
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 {
// 采用從底向上計(jì)算的方式加缘，計(jì)算出每個(gè)位置的最小和，一步步往上計(jì)算觉啊，到第一層時(shí)拣宏，就已經(jīng)計(jì)算出了所有的最小和，只需要遍歷第一行最小的數(shù)即可杠人。
r = A.count
if r > 0 {
list = A
c = A[0].count
var tmp = A
// 從倒數(shù)第二行開(kāi)始計(jì)算勋乾，因?yàn)榈箶?shù)第一行各個(gè)位置的最小和肯定是原值。
if r >= 2 {
var i = r - 2
while i >= 0 {
var j = 0
// 計(jì)算每個(gè)位置最小和
while j < c {
// 最小和
var minSum = Int.max
// 當(dāng)前位置的數(shù)
let n = tmp[i][j]
// 從其左邊一列起
var k = j - 1
// 遍歷起相鄰列嗡善，不超過(guò)1
while k <= j + 1 {
if k >= 0, k < c {
// 加上它下一行的數(shù)
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
