class Solution:
# @param triangle, a list of lists of integers
# @return an integer
# 9:11
# DP  count from bottom to top
def minimumTotal(self, triangle):
if not triangle:
return 0
lastLevel = triangle[1]
for i in range(len(triangle)  2, 1, 1):
for j in range(i + 1):
lastLevel[j] = min(lastLevel[j], lastLevel[j + 1]) + triangle[i][j]
return lastLevel[0]
Simple Python DP solution  O(n) 70ms


Also share my code in the opposite direction in adding the triangle~
But still I think the original post way would be more simple :)class Solution: # @param triangle, a list of lists of integers # @return an integer def minimumTotal(self, triangle): if not triangle: return 0 for d in range(1, len(triangle)): for idx in range(d+1): begin, end = max(0, idx1), min(d, idx+1) triangle[d][idx] += min(triangle[d1][begin:end]) return min(triangle[1])