1.题目描述
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
2.分析
- 第一步头脑发晕
- 第二步分析一下怎么样才能算是自顶向下。原来的数据结构类型和具有欺骗性，感觉比较复杂，进行一波变形。我们设定高为
h,长度为l你会发现其实自顶向下是上一层的一个值triangle[h][l]它向下的值为triangle[h+1][l]和triangle[h+1][l+1]，也就是正下方的一个值和一个左下方的一个值。也就是2下面的值是3和4;而3下面的值为6,5。
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
- 再经过一波变形，把金字塔倒过来,这个时候就更加清晰了，利用动态规划的思想，每一个值都加上其下一层（以原来正金字塔来说）的正下方和左下方的较小值，然后不断迭代上去。
[
[4,1,8,3],
[6,5,7],
[3,4],
[2]
]
[
[4,1,8,3],
[6,5,7],
[3,4],
[2]
]
- 需要注意一个点，这个金字塔结构其层数和每层列表中的元素数量是一致的。
3.解答
- 利用动态规划思想
- 因为最大使用的
j也就是开辟的列表的元素数量最大为最后一层元素数，又因为,这个金字塔结构其层数和每层列表中的元素数量是一致的。，所以满足题目的更高要求：
如果你可以只使用O(n)的额外空间（n为三角形的总行数）来解决这个问题，那么你的算法会很加分。
class Solution(object):
def minimumTotal(self, triangle):
if not triangle:
return 0
h = len(triangle) # 金字塔高度
lay = triangle[-1] # 取到金子塔最下面一层：是一个列表
i = h - 2 # 取到金字塔层数的倒数第二层： 是一个数字
while i >= 0:
j = 0 # j：遍历金字塔每一层中元素指针
while j <= i: # 本来行数和每层的元素数量是一致的，但索引从0开始所以减1，底下j有j+1所以再次减1，故直接是j<=i
lay[j] = min(lay[j], lay[j + 1]) + triangle[i][j] # 对上一层的一个值找其正下方和左下方的最小值，赋到其上
j += 1
i -= 1
return lay[0] # i为0时取到的是最上面一层，最上面一层只有一个值
