class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        s=[0]*(len(triangle)+1)
        for i in range(len(triangle)-1,-1,-1):
            for j in range(i+1):
                s[j]=min(s[j],s[j+1])+triangle[i][j]
        return s[0]

注意
1.s初始化n+1，各個(gè)邊界條件要注意
2.i從n-1開(kāi)始，由于s初始化為0，所以是s[j]初始化為a[i,j],不用寫(xiě)特殊處理代碼
3.range(start,stop[,step])，左閉右開(kāi)
4.自底向上的動(dòng)態(tài)規(guī)劃

重做,15分鐘一次通過(guò)，爽?。?/p>

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        tmp=[0]*(len(triangle[len(triangle)-1])+1)  # zh這個(gè)可以更簡(jiǎn)潔
        for i in reversed(triangle):
            for j,n in enumerate(i):
                tmp[j]=min(tmp[j],tmp[j+1])+n
        return tmp[0]

注意
1.reversed,反向迭代
2.enumerate ，既有數(shù)字也有序號(hào)

使用迭代，增加備忘錄存儲(chǔ)子問(wèn)題，每次使用這個(gè)方法的時(shí)候總會(huì)忘記存儲(chǔ)備忘錄，也忘記記錄備忘錄，等提交不通過(guò)才進(jìn)行改正

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        mem=[[-1]*(i+1) for i in range(len(triangle))]
        return self.dp(0,0,triangle,mem)
        
    def dp(self,i:int,j:int,triangle:List[List[int]],mem:List[List[int]]) ->int:
        if i==len(triangle)-1: 
            mem[i][j]=triangle[i][j]
            return mem[i][j]
        # 忘了從備忘錄讀取了，又光顧著取，忘了存了
        if(mem[i][j]!=-1):return mem[i][j]
        mem[i][j]=min(self.dp(i+1,j,triangle,mem),self.dp(i+1,j+1,triangle,mem))+triangle[i][j]
        return mem[i][j]

注意
1.三角矩陣的生成方式
2.備忘錄的存儲(chǔ)和讀取