借助python代码求三角形最小路径和

发布时间：2022-07-18 12:55:37 所属栏目：云计算来源：互联网

导读：哈喽！同学们，今天和大家分享一下，利用Python代码求三角形最小路径和！给定一个三角形，每一步只能移动到下一行中相邻的结点上，求出自顶向下的最小路径和。例如： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即：2 + 3 + 5 + 1 = 11

　　哈喽！同学们，今天和大家分享一下，利用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]

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

（编辑：开发网_开封站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

IBM 用混合云和AI 成就	云原生 PostgreSQL 集
领会 Kubernetes 网络	云计算成本节约的重点