```
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
#sum of all elements
n = len(triangle)
dp = [[0]*n for i in range(2)]
dp[0][0] = triangle[0][0]
for i in range(1,n):
i1 = i & 1 #current row
i0 = (i+1) & 1 # last row
dp[i1][0] = dp[i0][0] + triangle[i][0]
dp[i1][i] = dp[i0][i-1] + triangle[i][i]
for j in range(1,i):
dp[i1][j] = min(dp[i0][j-1],dp[i0][j])+triangle[i][j]
return min(dp[(n-1)&1])
```