利用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]

结语

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

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

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