image.png
120. 三角形最小路徑和
三角形最小路徑和
給定一個三角形形用，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上陷寝。
例如奉芦，給定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）骗奖。
說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個問題确徙，那么你的算法會很加分。
Python3 實現(xiàn)
動態(tài)規(guī)劃
#@author:leacoder
#@des: 動態(tài)規(guī)劃 三角形最小路徑和
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if triangle == None:
return 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])
# DP狀態(tài)方程：dp[i, j] = min(dp(i+1, j), dp(i+1, j+1)) + triangle[i, j]
return triangle[0][0]
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個人首頁：
https://www.zhihu.com/people/lichangke/
簡書個人首頁：
http://www.reibang.com/u/3e95c7555dc7
個人Blog:
https://lichangke.github.io/
歡迎大家來一起交流學習
