Python Bottom up DP O(n)+O(n) solution ( 5 lines )


  • 8
    J

    Source code worth thousand words:

    def minimumTotal(self, triangle):
        f = [0] * (len(triangle) + 1)
        for row in triangle[::-1]:
            for i in xrange(len(row)):
                f[i] = row[i] + min(f[i], f[i + 1])
        return f[0]]

  • 0
    Z

    I like your code, clean, and easily translated to other language


  • 0
    W

    thanks for such an elegant, fast, clean solution!!!


Log in to reply
 

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