My accepted python code using DP


  • 0
    S
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 1:
            return sum(triangle[0])
        
        total_level = len(triangle)
        level = 0
        result = self.dp(triangle,level, total_level)
        return result[0]
    
    def dp(self, triangle,level, total_level):
        if level == total_level-1:
            return triangle[total_level-1]
            
        result = [0] * (level+1)
        old_result = self.dp(triangle, level+1, total_level)
        for i in range(len(result)):
            result[i] = min(old_result[i],old_result[i+1]) + triangle[level][i]
        return result

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.