class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
dp = [[0] * (i + 1) for i in range(n)]
dp[0][0] = triangle[0][0]
for i in range(1, n):
dp[i][0] = dp[i - 1][0] + triangle[i][0]
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]
for j in range(1, i):
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
return min(dp[n - 1])
状态转移方程dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
,非常的直观,但是需要主要边界条件需要注意,即dp[i][0]和dp[i][i]
的取值是固定的,需要在进行每一层的dp之前/后额外写代码完成初始化,以免出现边界条件问题
优化成空间复杂度O(N)
的方法:
只需要维护两行的状态,而不是整个三角形的状态。我们可以使用两个一维数组,分别表示当前行和上一行的状态
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
dp = [0] * n
dp[0] = triangle[0][0]
for i in range(1, n):
dp[i] = dp[i - 1] + triangle[i][i] # 更新最右侧元素
for j in range(i - 1, 0, -1):
dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]
dp[0] = dp[0] + triangle[i][0] # 更新最左侧元素
return min(dp)
标签:triangle,min,int,路径,List,最小,range,三角形,dp
From: https://www.cnblogs.com/peterzh/p/18162069