LeetCode 题解工作台
最低票价
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车票有 三种不同的销售方式 ： 一张 为期一天 的通行证售价为 costs[0] 美元； 一张 为期七天 的通行证售价为 cos…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义一个函数 ，表示从第 次出行开始到最后一次出行结束所需的最小花费。那么答案为 。 函数 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 ：
- 一张 为期一天 的通行证售价为
costs[0]美元； - 一张 为期七天 的通行证售价为
costs[1]美元； - 一张 为期三十天 的通行证售价为
costs[2]美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。
示例 1：
输入：days = [1,4,6,7,8,20], costs = [2,7,15] 输出：11 解释： 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。 在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。 在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。 你总共花了 $11，并完成了你计划的每一天旅行。
示例 2：
输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] 输出：17 解释： 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。 在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 你总共花了 $17，并完成了你计划的每一天旅行。
提示：
1 <= days.length <= 3651 <= days[i] <= 365days按顺序严格递增costs.length == 31 <= costs[i] <= 1000
解题思路
方法一：记忆化搜索 + 二分查找
我们定义一个函数 ，表示从第 次出行开始到最后一次出行结束所需的最小花费。那么答案为 。
函数 的执行过程如下：
- 如果 ，表示所有出行已经结束，返回 ；
- 否则，我们需要考虑三种购买方式，分别是购买 天通行证、购买 天通行证和购买 天通行证。我们分别计算这三种购买方式的花费，并且利用二分查找，找到下一次出行的下标 ，然后递归调用 ，最后返回这三种购买方式的最小花费。
为了避免重复计算，我们使用记忆化搜索，将已经计算过的结果保存起来。
时间复杂度 ，空间复杂度 。其中 表示出行的次数。
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
ans = inf
for c, v in zip(costs, valid):
j = bisect_left(days, days[i] + v)
ans = min(ans, c + dfs(j))
return ans
n = len(days)
valid = [1, 7, 30]
return dfs(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(K) where K is the last travel day since each day requires constant-time computations for the three pass options. Space complexity is O(K) for storing dp values for each day. This avoids redundant recalculations and scales linearly with the range of travel days. |
| 空间 | O(K) |
面试官常问的追问
外企场景- question_mark
Are you considering all ticket durations for each travel day?
- question_mark
Can you optimize without checking every day from 1 to 365?
- question_mark
Do you correctly handle days not in the travel plan to skip unnecessary costs?
常见陷阱
外企场景- error
Failing to skip non-travel days, causing extra cost calculations.
- error
Incorrectly indexing dp for 7-day or 30-day passes, leading to out-of-bounds errors.
- error
Choosing a greedy approach instead of evaluating all pass options per travel day, which fails for overlapping passes.
进阶变体
外企场景- arrow_right_alt
Consider variations with different pass durations and costs, affecting state transitions.
- arrow_right_alt
Limit travel days to random sparse subsets, testing DP efficiency and correctness.
- arrow_right_alt
Use different cost structures, like discounted multi-pass bundles, changing the transition rules.