[LintCode 109] 数字三角形(Python)
题目描述
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
注意事项 如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。
样例 比如，给出下列数字三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
思路
自底向上遍历。并用一个辅助列表来记录当前行各点到底部的最小路径和。
代码
class Solution:
"""
@param: triangle: a list of lists of integers
@return: An integer, minimum path sum
"""
def minimumTotal(self, triangle):
# write your code here
res = 0
if triangle is None or len(triangle) == 0:
return res
# 从后往前遍历
# 辅助空间记录当前行各节点到底部的最小值
tmp = triangle[-1]
for i in range(len(triangle) - 1, -1, -1):
if i + 1 < len(triangle):
for j in range(len(triangle[i])):
tmp[j] = min(tmp[j], tmp[j + 1]) + triangle[i][j]
return tmp[0]
复杂度分析
时间复杂度 O(n2) ，空间复杂度 O(n) 。
