题目难度: 中等
原题链接
题目描述
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式：
一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天
【题目分析】
这道题目是 LeetCode 中的一道中等难度的动态规划问题，编号为 983，称为“最低票价”。问题的核心是找出在给定旅行天数列表（days）中，如何以最低成本购买三种不同类型的火车票：1天、7天和30天的通行证，以覆盖所有的旅行日期。
题目描述了一个场景，在一个热爱火车旅行的国家，你需要规划一年的旅行，旅行日期由数组 days 提供，数组中的每个元素都是从1到365的整数。三种火车票的价格分别存储在数组 costs 中，对应于1天、7天和30天的票价。
【解题策略】
为了解决这个问题，我们可以采用动态规划的方法。动态规划是一种处理具有重叠子问题和最优子结构特征的问题的有效方法。在这个问题中，我们定义一个动态规划数组 dp，其中 dp[i] 表示到达第 i 天所需的最低成本。
对于每一天，我们需要考虑三种购票策略：
1. 在当天购买1天的票。
2. 在之前某个日子购买7天的票，覆盖到当天。
3. 在之前某个日子购买30天的票，覆盖到当天。
我们需要找到在这三种策略中哪一种是最经济的，同时考虑到已经购买的票可以覆盖到当前日期。
【动态规划状态转移方程】
令 dp[i] 表示到达第 i 天的最低票价。状态转移方程可以表示为：
dp[i] = min(dp[i-1] + costs[0], dp[j] + costs[1], dp[k] + costs[2])
这里的 j 和 k 分别是 i 之前最近的日期，使得它们与 i 的时间间隔大于等于7和30天，表示这些日期购买的7天或30天票能覆盖到第 i 天。
【复杂度分析】
- 时间复杂度：O(N)，N 是 days 数组的长度。我们需要遍历每一天，同时在每一步中查找最近的合适购票日期，这个查找操作可以在 O(1) 内完成，所以总的时间复杂度是线性的。
- 空间复杂度：O(N)，我们需要一个长度为 N 的 dp 数组来存储每一天的最低票价。
【代码实现】
以下是一个用 Python 实现的动态规划解决方案：
```python
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
dp = [0] * len(days)
dp[0] = 0
for i in range(1, len(days)):
mncost = costs[0] if i == 0 else dp[i - 1] + costs[0]
for ci, duration in ((1, 7), (2, 30)):
for j in range(i - 1, -1, -1):
if days[i] - days[j] >= duration:
mncost = min(mncost, dp[j] + costs[ci])
break
dp[i] = mncost
return dp[-1]
```
这个 Python 代码中，首先初始化 dp 数组，然后逐天计算最低票价，通过遍历所有可能的购票选择并选择最低成本的策略。dp 数组的最后一个元素即为整个行程的最低票价。
总结来说，这道题目主要考察了动态规划的应用，以及如何处理具有时间依赖性的问题。通过理解题目所给条件和状态转移方程，我们可以有效地找到解决此类问题的算法，并实现代码来求解问题。
