Accepted O(n) memory, DP solution (Python)


  • 0
    M
    class Solution(object):
        def minimumTotal(self, triangle):
            """
            :type triangle: List[List[int]]
            :rtype: int
            """
            if len(triangle) == 0:
                return 0
    
            dp_prev = [None] * len(triangle)
            dp_curr = [None] * len(triangle)
            
            for row in reversed(triangle):
                # Make dp_prev 
                dp_prev, dp_curr = dp_curr, dp_prev
    
                # Update indx current
                for indx, elem in enumerate(row):
                    dp_curr[indx] = elem
                    minimum_adjacent = self.get_minimum_adjascent(indx, dp_prev)
                    if minimum_adjacent:
                        dp_curr[indx] += minimum_adjacent
    
            return dp_curr[0]
    
        def get_minimum_adjascent(self, indx, dp_prev):
            if indx+1 >= len(dp_prev):
                return None
            left_adj = dp_prev[indx]
            right_adj = dp_prev[indx + 1]
            return left_adj if left_adj < right_adj else right_adj

Log in to reply
 

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