Posted on 2023-06-25 22:30
Uriel 阅读(12)
评论(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