leetcode:三角形の最小パスと(python)

1.タイトルの説明
三角形を指定し、上から下への最小パスとを見つけます.各ステップは、次の行の隣接するノードにのみ移動できます.たとえば、三角形を指定します.

[
   [2],
  [3,4],
 [6,5,7],
[4,1,8,3]
]

上から下への最小経路和は11(すなわち2＋3＋5＋1＝11)である.
説明:
O(n)の余分な空間(nが三角形の総行数)だけを使ってこの問題を解決できれば、あなたのアルゴリズムはプラスになります.
2.考え方
ダイナミックプランニングにより,元の配列を直接修正したり,長さnのdp配列を用いて記録したりすることができる.
2.1元の配列に直接修正
三角形の下から上へ修正します.最後から2番目のレイヤから各レイヤを上に移動し、あるレイヤでは、このレイヤのすべての要素を最初から変更し、各ノードに左右のサブノード(サブパス)の小さな値を加算し、現在のノードを入れます.最初のレイヤまでレイヤごとに変更し、最初のレイヤを変更した後、最初のレイヤの(ノード)要素は私たちが要求する最小パスとなります.
2.1 pythonコード

2.2 1つの配列を利用して、元のデータを修正しない
現在のレイヤの前のレイヤ要素を格納する配列を使用し、dp配列の要素を移動後から変更します.dp[j]=triangle[i][j]+min(dp[j],dp[j+1])であり、jは現在のレイヤのj番目の要素の下付き文字を表す.このように、dp配列の値を1つ1つ変更します.最後にdp[0]を返します.異なるレイヤでは、修正されたdp配列の要素の個数も異なります.dp配列は三角形の最後の層データに初期化される.
2.2 pythonコード

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 0:
            return 0
        if len(triangle) == 1:
            return triangle[0][0]
        dp = triangle[len(triangle)-1]
        for row in range(len(triangle)-2,-1,-1):
            for col in range(len(triangle[row])):
                dp[col] = triangle[row][col] + min(dp[col],dp[col+1])
        return dp[0]