Leetcode 120. Triangle

https://leetcode.com/problems/triangle/

This is somewhat like DP, while the formula is clear: get the min from two adjacent elements.

Solution:

# T:O(m*n) S:O(1)
class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
        length = len(triangle)
        if length == 1:
            return triangle[0][0]
        for i in xrange(1, length):
            for j in xrange(len(triangle[i])):
                if j == 0:
                    triangle[i][j] = triangle[i - 1][j] + triangle[i][j]
                elif j == len(triangle[i])-1:
                    triangle[i][j] = triangle[i - 1][len(triangle[i-1])-1] + triangle[i][j]
                else:
                    triangle[i][j] = min(triangle[i-1][j], triangle[i-1][j-1]) + triangle[i][j]
        return min(triangle[length - 1])

Run Time: 96 ms