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

例如：

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

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

解決方案：

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

初始化：[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ì)算過(guò)程很簡(jiǎn)單，以dp[i]表示由第i+1層到第i層的第i個(gè)元素的最小路徑和，以j表示列數(shù)。dp[i]=下方與它相鄰的兩個(gè)值中的較小者的值+當(dāng)前元素值，比如min(4,1)+6=7;min(1,8)+5=6;最后的dp[0]就是路徑和的最小值。

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

完整代碼：

class Solution(object):

def minimumTotal(triangle):

# 獲取triangle的長(zhǎng)度，也就是‘三角形’的高

n = len(triangle)

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

dp = triangle[-1]

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

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

# 更改dp前j個(gè)的值

for j in range(i+1):

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

# 返回dp第一個(gè)值

return dp[0]

結(jié)語(yǔ)

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

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

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