Leetcode 3332. Maximum Points Tourist Can Earn
- Leetcode 3332. Maximum Points Tourist Can Earn
- 1. 解题思路
- 2. 代码实现
- 题目链接:3332. Maximum Points Tourist Can Earn
1. 解题思路
这一题思路上我就是一个暴力地动态规划,考察每一个时刻处在每一个城市时的最优选项。
2. 代码实现
给出python代码实现如下:
class Solution:def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:@lru_cache(None)def dp(i, u):if i >= k:return 0ans = stayScore[i][u] + dp(i+1, u)for v in range(n):if v == u:continueans = max(ans, travelScore[u][v] + dp(i+1, v))return ansreturn max(dp(0, i) for i in range(n))
提交代码评测得到:耗时11480ms,占用内存58.4MB。