leetcode-120-三角形最小路径和
题目描述:
第一次提交:动态规划
class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: n = len(triangle) for i in range(n-2,-1,-1): for j in range(0,i+1): triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]) return triangle[0][0]
另:不污染原数据
class Solution: def minimumTotal(self, triangle): l = len(triangle) if l == 0: return 0 dp = triangle[-1] for i in range(l - 2, -1, -1): for j in range(len(triangle[i])): dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j] return dp[0]