Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出每个城市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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理