题目:120. 三角形最小路径和
链接:https://leetcode-cn.com/problems/triangle
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 1 的两个结点。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 3 5 1 = 11)。 说明: 如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。
解题:
1、层次遍历。
代码:
代码语言:javascript复制class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
if len(triangle) == 0 or len(triangle[-1]) == 0:
return 0
dp = [0] * len(triangle[-1])
dp[0] = triangle[0][0]
for i in range(1, len(triangle)):
length = len(triangle[i])
dp[length - 1] = dp[length - 2] triangle[i][length - 1]
for j in range(length - 2, 0, -1):
dp[j] = min(dp[j - 1], dp[j]) triangle[i][j]
dp[0] = triangle[i][0]
return min(dp)
PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。
PPS:还是得日更呀,总结一下总是好的。