LeetCode 筆記 - 120. Triangle

題目在此 120. Triangle

給定一個三角形,請找出相加最小總和的路徑

解題思維

同學,這題本質是 Depth First Search 加上 Dynamic programming

如果有已經搜尋過的子三角形,就不用進去搜尋了
直接來看程式碼

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:

height = len(triangle)
if not triangle:
return 0
if height == 1:
return triangle[0][0]

dp = [[None for _ in range(len(y))] for y in triangle]

def dfs(index, layer):
if layer == height - 1:
return triangle[layer][index]

if dp[layer][index] is not None:
return dp[layer][index]

result_0 = dp[layer + 1][index] if dp[layer + 1][index] else dfs(index, layer + 1)
result_1 = dp[layer + 1][index + 1] if dp[layer + 1][index + 1] else dfs(index + 1, layer + 1)

dp[layer][index] = triangle[layer][index] + min(result_0, result_1)

return dp[layer][index]

result = triangle[0][0] + min(dfs(0, 1), dfs(1, 1))

return result

👍

也許你也會想看看