这道题目做了一天算是，出错的原因是，首先找最小路径要考虑他有负数，所以剪枝不行
然后改掉错误以后就超时了，代码如下：
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n = len(triangle)
if n == 0:
return 0
if n == 1:
return triangle[0][0]
temp = triangle[0][0]
minimum = [10000]
self.huisu(0,0,minimum, temp, triangle, n)
return minimum[0]
def huisu(self, i, j, minimum, temp,triangle, n):
if i == n - 1:
minimum[0] = min(minimum[0], temp)
return
#if temp > minimum[0]:
# return
if i + 1 < n and j <= i + 1:
self.huisu(i+1, j, minimum, temp + triangle[i+1][j], triangle, n )
if i + 1 < n and j + 1 <= i + 1:
self.huisu(i+1, j+1 , minimum, temp + triangle[i+1][j+1], triangle, n)
太愚蠢了，明明动态规划很明显，好吧从下面往上的动态规划，一个没有做过存储空间优化的版本，代码如下：
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n = len(triangle)
dp = [[0 for i in range(j + 1)] for j in range(n)]
for j in range(len(dp[-1])):
dp[-1][j] = triangle[-1][j]
for i in range(n-2,-1,-1):
for j in range(i+1):
dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j]
return dp[0][0]
优化过后，代码如下：
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n = len(triangle)
dp = [0 for i in range(n)]
for i in range(n):
dp[i] = triangle[-1][i]
for i in range(n-2,-1,-1):
for j in range(i+1):
dp[j] = min(dp[j],dp[j+1]) + triangle[i][j]
return dp[0]
