![Leetcode OJ : Triangle 动态规划 python solution Leetcode OJ : Triangle 动态规划 python solution](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
Total Accepted: 31557 Total Submissions: 116793
Given a triangle, find the minimum path sum from top to bottom.
Each step you may move to adjacent numbers on the row below.
[
[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.
简单的动态规划
import sys class Solution:
# @param triangle, a list of lists of integers
# @return an integer
def minimumTotal(self, triangle):
length = len(triangle)
l = [0]
l.extend([ sys.maxint for x in range(length - 1)])
def getLastSum(y, x):
return l[x] if x in range(y+1) else sys.maxint
for y in range(length):
for x in range(y, -1, -1):
l[x] = triangle[y][x] + min(getLastSum(y, x), getLastSum(y, x - 1))
return min(l)