LeetCode 120. 三角形最小路径和Python3思路动态规划自底向上从倒数第二行开始向上递推。对于位置 (i, j)它只能从下一行的 (i1, j) 或 (i1, j1) 走上来所以triangle[i][j] min(triangle[i1][j], triangle[i1][j1])这样一路推到顶部triangle[0][0] 就是最小路径和。如果不想修改原数组可以用一个一维 dp 数组保存下一行的结果。Python3 实现原地修改classSolution:defminimumTotal(self,triangle:List[List[int]])-int:# 自底向上原地修改foriinrange(len(triangle)-2,-1,-1):forjinrange(len(triangle[i])):triangle[i][j]min(triangle[i1][j],triangle[i1][j1])returntriangle[0][0]Python3 实现不修改原数组O(n) 额外空间classSolution:defminimumTotal(self,triangle:List[List[int]])-int:ifnottriangle:return0dptriangle[-1][:]# 复制最后一行foriinrange(len(triangle)-2,-1,-1):forjinrange(len(triangle[i])):dp[j]triangle[i][j]min(dp[j],dp[j1])returndp[0]关键点自底向上避免了处理边界和初始化问题最后直接返回顶部。状态转移dp[j] min(dp[j], dp[j1]) 当前值。空间优化一维 dp 不断被覆盖因为计算 dp[j] 时只需要下一行的 dp[j] 和 dp[j1]。原地修改法直接改 triangle额外空间 O(1)。复杂度· 时间O(n^2)n 为三角形行数每个元素访问一次。· 空间原地法 O(1)一维 DP 法 O(n)。测试用例minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]])# 11minimumTotal([[-10]])# -10minimumTotal([[-1],[2,3],[1,-1,-3]])# -1