数字三角形

xiaoxiao2021-02-28  17

给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

注意事项

如果你只用额外空间复杂度O(n)的条件下完成可以获得加分,其中n是数字三角形的总行数。

哪家公司问你的这个题? LinkedIn Airbnb Amazon Cryptic Studios Dropbox Epic Systems TinyCo Hedvig Uber Google Apple Facebook Bloomberg Zenefits Yelp Twitter Microsoft Yahoo Snapchat 感谢您的反馈 样例

比如,给出下列数字三角形:

[ [2], [3,4], [6,5,7], [4,1,8,3] ]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

说实话这个题属实是有难度,最一开始的想法是从最上端一条条的遍历,但是仔细想想这样又浪费时间又麻烦

想了好久没有思路,就看了看标签是动态提示,就百度了一下并学了学, http://blog.csdn.net/baidu_28312631/article/details/47418773

def minimumTotal(self, triangle): length = len(triangle) i = length - 1 while i > 0: for j in range(0,len(triangle[i - 1]),1): if triangle[i][j] < triangle[i][j + 1]: triangle[i - 1][j] += triangle[i][j] else: triangle[i - 1][j] += triangle[i][j+1] i -= 1 return triangle[0][0]
转载请注明原文地址: https://www.6miu.com/read-2400163.html

最新回复(0)