python DP solution.


  • 0
    M
        def minimumTotal(self, triangle):
            r = []
            for i in xrange(len(triangle)):
                r.append([])
                for j in xrange(len(triangle[i])):
                    r[i].append(triangle[i][j])
                    if i and j == 0:
                        r[i][j] += r[i-1][j]
                    elif i and j == i:
                        r[i][j] += r[i-1][j-1]
            for i in xrange(2, len(triangle)):
                for j in xrange(1, len(triangle[i])-1):
                    r[i][j] += min(r[i-1][j-1], r[i-1][j])
            return min(r[len(triangle)-1])
    

Log in to reply
 

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