哈嘍！同學們，今天和大家分享一下，利用Python代碼求三角形最小路徑和！給定一個三角形，每一步只能移動到下一行中相鄰的結點上，求出自頂向下的最小路徑和。

例如：

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

自頂向下的最小路徑和為 11(即：2 + 3 + 5 + 1 = 11)。

解決方案：

首先，這是一個一維動態(tài)規(guī)劃問題，動態(tài)規(guī)劃一般都是從下到上走。將dp數(shù)組初始化為‘三角形’最后一行的值，然后從倒數(shù)第二層開始向上，依次更改的dp數(shù)組中元素的個數(shù)，遍歷到第幾層就更改dp數(shù)組前面(那一層的長度)個。以問題描述中的例子為例：

初始化：[4,1,8,3]倒數(shù)第一層：[4,1,8,3]

第一次：[7,6,10,3]倒數(shù)第二層：[6,5,7]

第二次：[9,10,10,3]倒數(shù)第三層：[3,4]

第三次：[11,10,10,3]倒數(shù)第四層：[2]

計算過程很簡單，以dp[i]表示由第i+1層到第i層的第i個元素的最小路徑和，以j表示列數(shù)。dp[i]=下方與它相鄰的兩個值中的較小者的值+當前元素值，比如min(4,1)+6=7;min(1,8)+5=6;最后的dp[0]就是路徑和的最小值。

這個計算式子也就是狀態(tài)轉移方程：dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]

完整代碼：

class Solution(object):

def minimumTotal(triangle):

# 獲取triangle的長度，也就是‘三角形’的高

n = len(triangle)

# 初始化dp為‘三角形’最后那一行

dp = triangle[-1]

# 從下(倒數(shù)第二層)到上

for i in range(n-2, -1, -1):

# 更改dp前j個的值

for j in range(i+1):

dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]

# 返回dp第一個值

return dp[0]

結語

這是一道很簡單的動態(tài)規(guī)劃題目，主要思路就是找到狀態(tài)轉移函數(shù)。

動態(tài)規(guī)劃其實存在一定的套路。當求解的問題滿足以下條件時，就應該使用動態(tài)規(guī)劃：主問題的可分解為很多的子問題(可以利用遞歸求解)并且遞歸求解時，很多子問題的答案會被多次重復利用。例如：斐波那契數(shù)列。

版權聲明：轉載文章來自公開網(wǎng)絡，版權歸作者本人所有，推送文章除非無法確認，我們都會注明作者和來源。如果出處有誤或侵犯到原作者權益，請與我們聯(lián)系刪除或授權事宜。