# Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

# For example, given the following triangle
# [
     # [2],
    # [3,4],
   # [6,5,7],
  # [4,1,8,3]
# ]
# The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).


class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
		row = len(triangle)
		if row == 0:
			return None
		minV = [0 for i in xrange(len(triangle[row-1]))]
		for i in range(row-1,-1,-1):
			col = len(triangle[i])
			for j in range(0,col):
				if i == row - 1:
					minV[j] = triangle[i][j]
					continue
				minV[j] = min(minV[j],minV[j+1]) + triangle[i][j]
		return minV[0]