空间复杂度为n
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).
题目不难，但是判断细节好复杂
sum[i][j]=min(sum[i-1][j-1],sum[i-1][j])+triangle[i][j]
class Solution(object):
"""
:type triangle: List[List[int]]
:rtype: int
"""
def minimumTotal(self, triangle):
F = []
T = 0
for L in triangle:
for i in range(len(L)):
if i == 0: #the begin
if len(F) == 0:
T = L[i]
else:
T = F[i] + L[i]
elif i == len(L)-1: # the end\
S = T
T = F[i-1] + L[i]
F[i-1] = S
else:
S = T
if F[i] < F[i-1]:
T = F[i]+L[i]
else:
T =F[i-1]+L[i]
F[i-1] = S
F.append(T)
#find the min
Min = F[0]
for temp in F:
if temp < Min:
Min = temp
return Min
S = Solution()
print(S.minimumTotal([[-1],[2,3],[1,-1,-1]]))
改进，逆向思维
（1）在遍历每一行的时候可以从后往前，这样就省掉一个变量
（2）还可以从最底层向上变量，这样又简化了步骤
