leetcode 120 三角形最小路径和

把三角形看成一个上三角或者下三角(等腰三角形)，然后设置状态转移公式，当没到每行的最后一个的时候，以及每行的第一个，都可以有两种方法到达当前位置，选择最小的路径和。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:

        dp=[[0 for _ in range(len(triangle[-1]))] for i in range(len(triangle))]
        dp[0][0]=triangle[0][0]

        for i in range(1,len(triangle)):
            dp[i][0]=dp[i-1][0]+triangle[i][0]
        #dp[1][1]=triangle[0][0]+triangle[1][1]

        for i in range(1,len(triangle)):
            for j in range(1,i+1):
                if j==i:
                    dp[i][j]=dp[i-1][j-1]+triangle[i][j]
                else:
                    dp[i][j]=min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j])
        print(dp)
        return min(dp[len(triangle)-1])

空间优化，通过递减的方式实现仅使用一维数组的空间。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:

        dp=[0 for _ in range(len(triangle[-1]))]
        dp[0]=triangle[0][0]


        for i in range(1,len(triangle)):

            for j in range(i,-1,-1):
                if j==i:
                    dp[j]=dp[j-1]+triangle[i][j]
                elif j==0:
                    dp[0]=dp[0]+triangle[i][j]
                else:
                    dp[j]=min(dp[j-1]+triangle[i][j],dp[j]+triangle[i][j])

        return min(dp)