# Simple Python DP solution - O(n) 70ms

• ``````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]``````

• I think of the similar way, but I keep adding value to the previous row instead of simply add it to the last row. Therefore, I need to further check with the boundary. Although the result is the same, yours is more simple _ Thanks for sharing!

• 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, idx-1), min(d, idx+1)
triangle[d][idx] += min(triangle[d-1][begin:end])
return min(triangle[-1])
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.