Medium.
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).
Note:
Bonus point if you are able to do this using only O(n) extra space,
where n is the total number of rows in the triangle.
class Solution():
def minimumTotal(self, x):
if not x:
return 0
way = [0] * len(x)
way[0] = x[0][0]
for i in range(1, len(x)):
for j in range(len(x[i])-1, -1, -1):
if j == len(x[i]) - 1:
way[j] = way[j-1] + x[i][j]
elif j == 0:
way[j] = way[j] + x[i][j]
else:
way[j] = min(way[j-1], way[j]) + x[i][j]
return min(way)