打卡群刷题总结0816——三角形最小路径和

2020-08-17 17:25:39 浏览数 (1)

题目: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:还是得日更呀,总结一下总是好的。

ps

0 人点赞