LeetCode刷题笔记：字节跳动-动态或贪心(4)-三角形最小路径和

5.三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

本题建立了一个dp三角形，代表当前节点的最小路径和。自上而下、从左到右对三角形进行遍历。dp[i][j]是dp[i-1][j]和dp[i-1][j-1]中的最小值加上triangle[i][j]。最后返回dp[-1]中的最小值即可。代码如下：

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        l = len(triangle)
        dp = [[0 for i in range(x)] for x in range(1,l+1)]
        dp[0][0]=triangle[0][0]
        for i in range(1,l):
            dp[i][0]=dp[i-1][0]+triangle[i][0]
            dp[i][i]=dp[i-1][i-1]+triangle[i][i]
        for i in range(1,l):
            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[l-1])