題目在此 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
|
👍
相關文章