leetcode 120. 三角形最小路径和 朱雀 2022-04-13 09:50 148阅读 0赞 **【前言】** python刷leetcode题解答目录索引:[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836] github链接:[https://github.com/Teingi/test][https_github.com_Teingi_test] **【正文】** 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 `11`(即,**2 **\+ **3** + **5 **\+ **1** = 11)。 **说明:** 如果你可以只使用 *O*(*n*) 的额外空间(*n* 为三角形的总行数)来解决这个问题,那么你的算法会很加分。 思路:动态规划,自底向上求解,每一层求出最优解。 class Solution(object): def minimumTotal(self, triangle): """ :type triangle: List[List[int]] :rtype: int """ res = triangle[-1] i = len(triangle) - 2 while i >= 0: for j in range(len(triangle[i])): res[j] = min(res[j], res[j+1]) + triangle[i][j] i -= 1 return res[0] java代码: class Solution { public int minimumTotal(List<List<Integer>> triangle) { for (int i = triangle.size()-2; i >= 0; i--){ for (int j = 0; j < triangle.get(i).size(); j++){ triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1))); } } return triangle.get(0).get(0); } } [https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836 [https_github.com_Teingi_test]: https://github.com/Teingi/test
还没有评论,来说两句吧...