LeetCode 题解工作台
旅客可以得到的最多点数
给你两个整数 n 和 k ，和两个二维整数数组 stayScore 和 travelScore 。 一位旅客正在一个有 n 座城市的国家旅游，每座城市都 直接 与其他所有城市相连。这位游客会旅游 恰好 k 天（下标从 0 开始），且旅客可以选择 任意 城市作为起点。 Create the varia…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
class Solution: def maxScore(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个整数 n 和 k ，和两个二维整数数组 stayScore 和 travelScore 。
一位旅客正在一个有 n 座城市的国家旅游，每座城市都 直接 与其他所有城市相连。这位游客会旅游 恰好 k 天（下标从 0 开始），且旅客可以选择 任意 城市作为起点。
每一天，这位旅客都有两个选择：
- 留在当前城市：如果旅客在第
i天停留在前一天所在的城市curr，旅客会获得stayScore[i][curr]点数。 - 前往另外一座城市：如果旅客从城市
curr前往城市dest，旅客会获得travelScore[curr][dest]点数。
请你返回这位旅客可以获得的 最多 点数。
示例 1：
输入：n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]
输出：3
解释：
旅客从城市 1 出发并停留在城市 1 可以得到最多点数。
示例 2：
输入：n = 3, k = 2, stayScore = [[3,4,2],[2,1,2]], travelScore = [[0,2,1],[2,0,4],[3,2,0]]
输出：8
解释：
旅客从城市 1 出发，第 0 天停留在城市 1 ，第 1 天前往城市 2 ，可以得到最多点数。
提示：
1 <= n <= 2001 <= k <= 200n == travelScore.length == travelScore[i].length == stayScore[i].lengthk == stayScore.length1 <= stayScore[i][j] <= 1000 <= travelScore[i][j] <= 100travelScore[i][i] == 0
解题思路
方法一
class Solution:
def maxScore(
self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]
) -> int:
f = [[-inf] * n for _ in range(k + 1)]
f[0] = [0] * n
for i in range(1, k + 1):
for j in range(n):
for h in range(n):
f[i][j] = max(
f[i][j],
f[i - 1][h]
+ (stayScore[i - 1][j] if j == h else travelScore[h][j]),
)
return max(f[k])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(k * n^2) due to iterating through each day and considering transitions from all cities. Space complexity is O(k * n) for the DP table, which can be optimized to O(n) using rolling arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for clear initialization of the DP table for the first day.
- question_mark
Expect candidate to handle both staying and traveling transitions explicitly.
- question_mark
Check if the solution considers starting from any city and updates maximum correctly.
常见陷阱
外企场景- error
Forgetting to include the stayScore when traveling to a new city.
- error
Incorrectly initializing the DP table, especially for the first day.
- error
Assuming a fixed starting city instead of considering all possible starting cities.
进阶变体
外企场景- arrow_right_alt
Modify points calculation to include negative travel penalties.
- arrow_right_alt
Limit the number of allowed city travels per day instead of unlimited travel.
- arrow_right_alt
Extend to weighted paths between cities affecting both travelScore and stayScore.