LeetCode .120. 三角形最小路径和 - 详解 Dear 丶 2022-03-18 04:14 142阅读 0赞 ### 题目描述 ### 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 说明： 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。 ### 解法 ### DP 思路： * 递归 + 记忆化 * 状态的定义 dp\[n\] * dp 状态转移方程 dp\[n\] = best\_of(dp\[n-1\] , dp\[n-2\],…) 本题中： * 状态的定义： res\[j\] 为从底部开始，到\[i,j\] 整个路径上最小的总和 * dp 状态转移方程： res \[j\] = min(res\[j\], res\[j+1\]) + triangle\[i\]\[j\] triangle = n 行 m长(底部) * 时间复杂度O(m\*(n-2)) ~= (m\*n) 符合只使用 O(n) 的额外空间（n 为三角形的总行数）的要求 def minimumTotal(self, triangle): if not triangle: return 0 res = triangle[-1] for i in range(len(triangle) - 2, -1, -1): for j in range(len(triangle[i])): res[j] = min(res[j], res[j+1]) + triangle[i][j] return res[0] 本题不可以用贪心的解法
还没有评论，来说两句吧...