利用python代码求三角形最小路径和

哈喽!同学们,今天和大家分享一下,利用Python代码求三角形最小路径和!给定一个三角形,每一步只能移动到下一行中相邻的结点上,求出自顶向下的最小路径和。

例如:

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

自顶向下的最小路径和为 11(即:2 + 3 + 5 + 1 = 11)。

解决方案:

首先,这是一个一维动态规划问题,动态规划一般都是从下到上走。将dp数组初始化为‘三角形’最后一行的值,然后从倒数第二层开始向上,依次更改的dp数组中元素的个数,遍历到第几层就更改dp数组前面(那一层的长度)个。以问题描述中的例子为例:

初始化:[4,1,8,3]倒数第一层:[4,1,8,3]

第一次:[7,6,10,3]倒数第二层:[6,5,7]

第二次:[9,10,10,3]倒数第三层:[3,4]

第三次:[11,10,10,3]倒数第四层:[2]

计算过程很简单,以dp[i]表示由第i+1层到第i层的第i个元素的最小路径和,以j表示列数。dp[i]=下方与它相邻的两个值中的较小者的值+当前元素值,比如min(4,1)+6=7;min(1,8)+5=6;最后的dp[0]就是路径和的最小值。

这个计算式子也就是状态转移方程: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]

# 从下(倒数第二层)到上

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]

结语

这是一道很简单的动态规划题目,主要思路就是找到状态转移函数。

动态规划其实存在一定的套路。当求解的问题满足以下条件时,就应该使用动态规划:主问题的可分解为很多的子问题(可以利用递归求解)并且递归求解时,很多子问题的答案会被多次重复利用。例如:斐波那契数列。

版权声明:转载文章来自公开网络,版权归作者本人所有,推送文章除非无法确认,我们都会注明作者和来源。如果出处有误或侵犯到原作者权益,请与我们联系删除或授权事宜。

相关新闻