題目說明:給你一個三角形的陣列，要求出從最上層到最底層的最小總和，要注意的是往下加的時候橫列的位置只能維持和原本一樣或是往右一格。

Case 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Case 2:
Input: triangle = [[-10]]
Output: -10

解題思路：雖然說題目是要求從上層到下層的最小總和，但我們採用的方法是bottom-up的策略。從底層開始一路往上加並挑選出較小的值，最後得到就是答案。以下直接用case 1進行說明
2 --第0層
3 4 --第1層
6 5 7 --第2層
4 1 8 3 --第3層

step 1:第2層的6挑選4,1之間的較小值
step 2:第2層的5挑選1,8之間的較小值
step 3:第2層的7挑選8,3之間的較小值
剩下的第0層和第1層以此類推

因此我們可以得到以下的結論：

1. 若traingle矩陣的長度=1，直接回傳第0個
2. 若triangle矩陣的長度>1，從倒數第二層開始的每個元素加上其下一層同樣橫列位置以及橫列位置右一格的元素，持續迭代到第0層

用虛擬碼(pseudo code)表示可以寫成以下:

minsum(triangle){
    if(triangle.length==0){
        return triangle[0]
    }
    else{
    for i=triangle.length-2 to 0{
        for j=0 to triangle[i].length-1{
            triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1])
        }
       }
       return triangle[0][0]
    }
}

附上程式碼
Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle)==1:
            return trinagle[0][0]#min(triangle[0])也可
        for i in range(len(triangle)-2,-1,-1):
            for j in range(len(triangle[i])):
                triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1])
        return triangle[0][0]

遇到動態規劃(dynamic programming)的題目建議在電腦旁邊準備紙筆，可以把矩陣、遞迴式子用畫的或寫出來比較方便思考而且比較容易找到規律，單純用腦袋直接憑空思考實在是有些困難，簡單一點的題目或許還可以直接思考，但難度提升以後就很難直接做到。