題目連結(jié)：
題目意譯：
給定一個陣列 triangle，回傳從頂部到底部的最小路徑和。
對於每一步，你可以移動到下一列的相鄰數(shù)字。更正式地，如果你位於當(dāng)前列的索引值 i 之位置，你可以移動到下一列的索引值 i 或是 i + 1 之位置。
限制：
1 ≦ triangle.length ≦ 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10 ^ 4 ≦ triangle[i][j] ≦ 10 ^ 4
進(jìn)階： 你可以完成此題藉由 O(n) 的額外空間嗎？其中 n 為陣列 triangle 的列數(shù)。
範(fàn)例測資：
範(fàn)例 1：
輸入： triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出： 11
解釋： triangle 看起來像是以下：
2
3 4
6 5 7
4 1 8 3
從頂?shù)降椎淖钚÷窂胶蜑?2 + 3 + 5 + 1 = 11 （如上之底線所標(biāo)示數(shù)字）
範(fàn)例 2：
輸入： triangle = [[-10]]
輸出： -10
解題思維：
定義 D[i][j] 為走到第 i 列第 j 個位置的最小路徑和。
根據(jù)題意，我們可以得到遞迴式
D[i][j] = min(D[i - 1][j - 1], D[i - 1][j]) + triangle[i][j]
且觀察後可得初始條件
D[0][0] = triangle[0][0]
因此，我們可以從第 1 列開始推得所有索引值 j 的 D[1][j] ，進(jìn)而推得第 2 列的所有位置 j 的 D[2][j]……以此類推。
而最後我們只須看哪個位置 j 的 D[n - 1][j] 之值（n 為 triangle 之列數(shù)）最小，即是所求。
至於如果要將空間複雜度變?yōu)?O(n)，可以藉由交錯使用兩個長度為 n 之陣列。例如計算 D[2][j] 使用第一個陣列、D[3][j] 使用第二個、D[4][j] 回頭使用第一個等等。這樣便不需要開滿 n 個長度為 n 的陣列，使得空間複雜度為 O(n ^ 2) 了。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
