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

例如：

[

[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]

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

這個計(jì)算式子也就是狀態(tài)轉(zhuǎn)移方程：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]

結(jié)語

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

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

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