Python DP iteratively Solution with O(n) Space Complexity


  • 0
    I

    I think the idea is not that hard to comprehend.

    Note that the res_list with size n stores all possible path sums from the top root to n-th layer nodes so that we can return min(res_list) as the result to the problem.

    And here is my code below.

        def minimumTotal(self, triangle):
    
            # Time Complexity:  O(m)
            # Space Complexity: O(one n)
    
            n = len(triangle)
            res_list = [0] * n
    
            for row in triangle:
                for i in range(len(row)):
                    if i == 0:
                        t=res_list[i]
                        res_list[i] = res_list[i] + row[i]
                    elif i == len(row) - 1:
                        res_list[i] = t + row[i]
                    else:
                        t1 = res_list[i]
                        res_list[i] = min(t + row[i], res_list[i] + row[i])
                        t=t1
    
            return min(res_list)
    

Log in to reply
 

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