LeetCode 三角形最小路径和题解

LeetCode 三角形最小路径和题解题目描述给定一个三角形找到从顶到底的最小路径和。示例输入triangle [[2],[3,4],[6,5,7],[4,1,8,3]]输出11解题思路方法动态规划思路使用动态规划从底部向上计算。dp[i][j] 表示从底部到 (i,j) 的最小路径和。dp[i][j] min(dp[i1][j], dp[i1][j1]) triangle[i][j]。复杂度分析时间复杂度O(n^2)。空间复杂度O(n)。代码实现def minimum_total(triangle): n len(triangle) dp triangle[-1][:] for i in range(n - 2, -1, -1): for j in range(i 1): dp[j] min(dp[j], dp[j 1]) triangle[i][j] return dp[0] # 测试 def test_minimum_total(): triangle [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] print(minimum_total(triangle)) # 输出11 if __name__ __main__: test_minimum_total()总结三角形最小路径和是动态规划的典型应用从底部向上计算最小路径和。