Posted on 2023-06-25 22:30
Uriel 閱讀(48)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
遞歸 & 分治 、
閑來無事重切Leet Code
給出每個城市i的locations[i]，以及起始、終點城市和初始汽油量，從城市i到j需要耗費汽油｜locations[i]-locations[j]｜，問一共有多少條路線
遞歸DP+memorization（用python3的lru_cache）
參考了Discussion -> https://leetcode.com/problems/count-all-possible-routes/solutions/3678855/python3-solution/
1 #1575
2 #Runtime: 2024 ms (Beats 68.42%)
3 #Memory: 41.4 MB (Beats 12.3%)
4
5 class Solution:
6 def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
7 MOD = 10 ** 9 + 7
8
9 @lru_cache(None)
10 def DP(p, x):
11 if x < 0:
12 return 0
13 t = 0
14 if p == finish:
15 t += 1
16 for i in range(len(locations)):
17 if i != p:
18 t += DP(i, x - abs(locations[i] - locations[p]))
19 return t
20
21 return DP(start, fuel) % MOD