Simple Python DP solution - O(n) 70ms


  • 0
    G
    class Solution:
        # @param triangle, a list of lists of integers
        # @return an integer
        # 9:11
        # DP - count from bottom to top
        def minimumTotal(self, triangle):
            if not triangle:
                return 0
    
            lastLevel = triangle[-1]
            for i in range(len(triangle) - 2, -1, -1):
                for j in range(i + 1):
                    lastLevel[j] = min(lastLevel[j], lastLevel[j + 1]) + triangle[i][j]
    
            return lastLevel[0]

  • 0
    O

    I think of the similar way, but I keep adding value to the previous row instead of simply add it to the last row. Therefore, I need to further check with the boundary. Although the result is the same, yours is more simple _ Thanks for sharing!


  • 0
    O

    Also share my code in the opposite direction in adding the triangle~
    But still I think the original post way would be more simple :)

    class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
        if not triangle:
            return 0
        for d in range(1, len(triangle)):
            for idx in range(d+1):
                begin, end = max(0, idx-1), min(d, idx+1)
                triangle[d][idx] += min(triangle[d-1][begin:end])
        return min(triangle[-1])
    

Log in to reply
 

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