這題要從一個三角形數組的頂部到底部找最小路徑和，而且每一步只能移到下一行的相鄰位置。目標是找出一個解法，在可以的情況，優化空間複雜度到 O(n)，n 是三角形的行數。

思路：
這是常見的動態規劃問題，目標是逐步算到每一行某位置的最小路徑和，可以從下往上算，這樣每次算都可以直接用已經算好的結果。

步驟：
動態規劃狀態定義，定義 dp[i][j] 是從三角形的頂到位置 (i, j) 的最小路徑和，結果要的是 dp[0][0]，就是從頂到底的最小路徑和，狀態轉移方程，每個位置 dp[i][j] 可從前一行的 dp[i-1][j] 或 dp[i-1][j-1] 轉移來，所以dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]，空間優化，因為只要當前行和下一行的數據，所以可直接在原地更新最小路徑和，不用額外的儲存空間。

程式碼：
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
#從倒數第二行開始，逐行向上處理
for row in range(len(triangle) - 2, -1, -1):
# 遍歷該行的每個元素，更新最小路徑和
for col in range(len(triangle[row])):
# 更新當前元素為該元素加上它下面相鄰兩個元素中較小的那個
triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])

    #最終最小的路徑和會儲存在三角形頂部的元素
    return triangle[0][0]

解釋：
第一個 for 迴圈，for row in range(len(triangle) - 2, -1, -1)，從倒數第二行開始，往上處理，這樣可以逐步縮小三角形，算每個位置的最小路徑和。第二個 for 迴圈，for col in range(len(triangle[row]))，遍歷當前行的每個元素，更新每個元素的值，最小路徑和的更新，triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]) 對於當前元素，加上它下一行的相鄰兩個元素中的較小值，這樣可以確定當前元素保存了從該點到底部的最小路徑和，最後的返回值，return triangle[0][0]，整個三角形處理完，最頂的元素會包含最小的路徑和，直接返回這個值。
時間複雜度：O(n^2)因為要遍歷每個元素一次，n 是三角形的高。
空間複雜度：O(1)，直接在原地更新三角形數組，所以額外的空間複雜度是常數。

心得：
這題問題是一個典型的動態規劃問題，目的是找出從三角形頂端到底部的最小路徑和，對我來說，學這題有助於了解動態規劃的想法，尤其是怎樣透過從底網上的方式來ㄧㄧ解決問題。重點在每個位置的選擇要根據之前算的結果，所以從倒數第二行開始往上算，慢慢縮小問題範圍，最後在頂端得出答案。
解題過程，我了解了動態規劃「重疊子問題」和「最優子結構」的概念，每行的最小路徑和取決於下一行相鄰兩個元素的最小值，這樣可以用前面算好的結果來優化後面的決策，順便讓我重新複習數據結構原地修改的能力，原地修改不用額外的空間，直接用輸入數據來更新和存儲結果，感覺就蠻常會用到的。