Skip to content

120 Triangle

120. Triangle

题目:

https://leetcode.com/problems/triangle/

难度: Medium

思路:

先是要注意下这句话:Each step you may move to adjacent numbers on the row below

在考虑adjacent number的定义,并不是角标的adjacent,而是真的形态上的adjacent

比如

        -1                              -1
    2       1           最小          1       0
-2      2       0               -1      2       0

最小是-1, 而并不能从第二排的0跳到第三排的第一个造成-2.

so AC代码

感觉关于dp,我可能还需要补一些东西,因为我不能做到O(n) space

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        # n total rows of triangle
        n = len(triangle)
        if n == 1: return triangle[0][0]
        elif n == 2 : return min(triangle[0][0] + triangle[1][0], triangle[0][0] + triangle[1][1])
        else:
            res = []
            for i in range(n):
                res.append(triangle[i])

            res[0] = [triangle[0][0]]
            res[1] = [triangle[0][0] + triangle[1][0], triangle[0][0] + triangle[1][1]]

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

            return min(res[-1])


回到顶部