[LeetCode]120. 三角形最小路径和(Triangle)

题目描述

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

解题思路

动态规划。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
length = len(triangle)
if length == 0:
return 0
dp = [0] * length
dp[0] = triangle[0][0]
for i in range(1, length):
tmp = [float("inf")] * (i + 1)
for j in range(len(tmp)):
if j > 0:
tmp[j] = min(tmp[j], dp[j - 1] + triangle[i][j])
if j < len(tmp) - 1:
tmp[j] = min(tmp[j], dp[j] + triangle[i][j])
dp[:len(tmp)] = tmp
return min(dp)