Lint 109. Triangle

Description

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Solution

只使用DP O(2^N) 会超时

class Solution:
    """
    @param triangle: a list of lists of integers
    @return: An integer, minimum path sum
    """
    '''
    [1]
    [2,3]
    [3,4,5]
    [6,7,8,9]
    '''
    
    def calculate_total(self,triangle,x,y):
        if x == len(triangle):
            return 0
        left = self.calculate_total(triangle,x+1,y)
        right = self.calculate_total(triangle,x+1,y+1)
        return min(left, right) + triangle[x][y]

    def minimumTotal(self, triangle):
        return self.calculate_total(triangle,0,0)

使用记忆化搜索+DP可使复杂度 O(2^N) --> O(N^2) N为树的高度 (避免重复搜索)

class Solution:
    """
    @param triangle: a list of lists of integers
    @return: An integer, minimum path sum
    """
    '''
    [1]
    [2,3]
    [3,4,5]
    [6,7,8,9]
    '''
    
    def calculate_total(self,triangle,x,y):
        if x == len(triangle):
            return 0
        if (x,y) in self.memo:
            return self.memo[(x,y)]
        
        left = self.calculate_total(triangle,x+1,y)
        right = self.calculate_total(triangle,x+1,y+1)
        self.memo[(x,y)] = min(left, right) + triangle[x][y]
        return self.memo[(x,y)]
    def minimumTotal(self, triangle):
        self.memo = dict()
        # write your code here
        return self.calculate_total(triangle,0,0)