pythonを使用してleetcode 120三角形の最小パスと
三角形を指定し、上から下への最小パスとを見つけます.各ステップは、次の行の隣接するノードにのみ移動できます.
たとえば、三角形を指定します.
[[2],[3,4],[6,5,7],[4,1,8,3]]上から下への最小経路和は11(すなわち,2+3+5+1=11)である.
説明:
O(n)の余分な空間(nが三角形の総行数)だけを使ってこの問題を解決できれば、あなたのアルゴリズムはプラスになります.構想の最も基礎的な動的計画は,triangle[b][a]で到達(b,a)の最小経路和を格納し,(b+1,a)と(b+1,a+1)からしか到達できないのでtriangle[b][a]=triangle[b][a]+min(triangle[b+1][a],triangle[b+1][a+1])コード
たとえば、三角形を指定します.
[[2],[3,4],[6,5,7],[4,1,8,3]]上から下への最小経路和は11(すなわち,2+3+5+1=11)である.
説明:
O(n)の余分な空間(nが三角形の総行数)だけを使ってこの問題を解決できれば、あなたのアルゴリズムはプラスになります.構想の最も基礎的な動的計画は,triangle[b][a]で到達(b,a)の最小経路和を格納し,(b+1,a)と(b+1,a+1)からしか到達できないのでtriangle[b][a]=triangle[b][a]+min(triangle[b+1][a],triangle[b+1][a+1])コード
def minimumTotal(self, triangle):
nums=triangle
if nums==[[]]:return 0
for b in range(len(nums)-2,-1,-1):
for a in range(len(nums[b])):
nums[b][a]=nums[b][a]+min(nums[b+1][a],nums[b+1][a+1])
return triangle[0][0]