from typing import Listclass Solution: def minimumTotal1(self, triangle: List[List[int]]) -> int: return self.dfs(triangle,0,0,len(triangle),0) # 深搜的做 ...
from typing import List
class Solution:
def minimumTotal1(self, triangle: List[List[int]]) -> int:
return self.dfs(triangle,0,0,len(triangle),0)
# 深搜的做法，這個做法是錯誤的，
# 我本來的想法是按照遍歷每一層的最小值。但是是行不通的
def dfs(self,num_list,position,depth,maxdepth,min_sum):
# 遞歸函數的出口
if depth == maxdepth:
return min_sum
# 列表的第一層只有一個數。
if depth == 0:
min_sum += num_list[depth][position]
return self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
# 後邊分三種情況討論，
if depth != 0:
if num_list[depth][position] > num_list[depth][position + 1]:
min_sum += num_list[depth][position + 1]
position += 1
return self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
elif num_list[depth][position] < num_list[depth][position + 1]:
min_sum += num_list[depth][position]
return self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
else:
min_sum1 = self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
min_sum2 = self.dfs(num_list,position + 1,depth + 1,maxdepth,min_sum)
if min_sum1 > min_sum2:return min_sum2
else:return min_sum1
# 正確的做法是使用動態規劃的方法。
# 計算出每一條路徑的最小值
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 進行雙重迴圈遍歷，
for index1 in range(1,len(triangle)):
for index2 in range(index1 + 1):
# 每層列表開頭和結尾，只可能是上一層列表的開頭結尾走到。
if index2 == 0:
triangle[index1][index2] += triangle[index1 - 1 ][index2]
elif index1 == index2:
triangle[index1][index2] += triangle[index1 - 1][index2 - 1]
# 每一層其他位置只可能由上一層的當前位置和左邊一個位置走到
else:
triangle[index1][index2] += min(triangle[index1 -1][index2],triangle[index1 - 1][index2 - 1])
return min(triangle[-1])
A = Solution()
print(A.minimumTotal([[2],
[3,4],
[6,5,7],
[4,1,8,3]]))
