```
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
if not triangle:
return 0
n = len(triangle)
if n == 1:
return triangle[0][0]
prev = triangle[0]
for i in xrange(1, n):
current = [0]*(i+1)
for j in xrange(i+1):
if j == 0: current[0] = triangle[i][0] + prev[0]
elif j == i: current[i] = triangle[i][i] + prev[-1]
else:
current[j] = min(triangle[i][j] + prev[j-1], triangle[i][j] + prev[j])
prev = current
return min(current)
```