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。