6-line python algorithm with space complexity being O(sqrt(n)), time complexity being O(n)


  • 0
    A
    class Solution:
        # @param triangle, a list of lists of integers
        # @return an integer
        def minimumTotal(self, triangle):
            if triangle is None:
                return
    
            t_len = len(triangle)
            res = triangle[-1][:]
            for lv in triangle[-2::-1]:
                for i in range(len(lv)):
                    res[i] = min(res[i]+lv[i],res[i+1]+lv[i])
    
            return res[0]

Log in to reply
 

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