【算法题】120. 三角形最小路径和-力扣(LeetCode)
【算法题】120. 三角形最小路径和-力扣(LeetCode)
1.题目
下方是力扣官方题目的地址
给定一个三角形 triangle
,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i
,那么下一步可以移动到下一行的下标 i
或 i + 1
。
示例 1:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
示例 2:
输入:triangle = [[-10]]
输出:-10
提示:
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
2.题解
思路
我们以triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
为例
[2]
[3,4]
[6,5,7]
[4,1,8,3]
这题要求从三角形最顶层到最底层的最小路径和。
如何没有要求,我们在每一层中选出一个最小的数出来,进行累加就行了。
不过这题要求每一步只能移动到下一行中相邻的结点上
。就这一句话,就显然说明了当前这步是由上一行所决定而来的。
那么具体点呢?
当前行的这一步是由它的上方或者左上方走过来的。
比如说:要想走到5
这里,你必须经过3
或者4
。
当然,我们还需要考虑一些特殊的地方:
最顶层的一个元素和之后的每一行中首尾两个元素。
因为最顶层的上方左上方都没元素了。
而之后的每一行中的首尾两个元素的左上方没有元素了。
考虑到这些,我们用dp[i][j]
来表示从三角形顶部走到位置(i,j)的最小路径和。
我们结合下方的dp
图:
就很容易地可以得出状态转移方程:
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
至于这些前面谈到的特殊元素,因为它们的路径都是固定只有一个点可以到达,所以我们可以直接给它们赋上值:
dp[0][0]=triangle[0][0]
for i in range(1,n):
dp[i][0]=triangle[i][0]+dp[i-1][0]
dp[i][i]=triangle[i][i]+dp[i-1][i-1]
Python代码
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n=len(triangle)
dp=[[0]*(x+1) for x in range(n)] # 初始化dp数组
dp[0][0]=triangle[0][0]
for i in range(1,n):
dp[i][0]=triangle[i][0]+dp[i-1][0] # 将这些特殊元素直接赋上值
dp[i][i]=triangle[i][i]+dp[i-1][i-1]
for i in range(1,n):
for j in range(1,i):
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j] # 利用状态转移方程
return min(dp[n-1])
3.结语
本人资历尚浅,发博客主要是记录与学习,欢迎大佬们批评指教!大家也可以在评论区多多交流,相互学习,共同成长。
原文地址:https://blog.csdn.net/Janium/article/details/142334381
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!