更新题目 983. Minimum Cost For Tickets

题目 lc983 · 修改（rev 2） · cc · 2026-10-26 23:11
body

@@ -1,5 +1,12 @@
 ## 题目
 
-一年里要出行的日子 `days`（升序），票有三种：1 天、7 天、30 天，价格 `costs`。求覆盖所有出行日的最低花费。
+给一年里要出行的日子 `days`（严格递增，每个数在 1 到 365 之间），和三种通票的价格 `costs = [c1, c7, c30]`，分别是 1 天票、7 天票、30 天票。一张 7 天票从买的那天起连续管 7 天（第 2 天买，管第 2 到第 8 天）。求让每个出行日都有票的最低总花费。
+
+| 输入 | 输出 | 怎么买 |
+| --- | --- | --- |
+| `days = [1, 4, 6, 7, 8, 20]`，`costs = [2, 7, 15]` | `11` | 第 1 天买 1 天票，第 4 天买 7 天票管到第 10 天，第 20 天买 1 天票，2 + 7 + 2 = 11 |
+| `days = [1, 2, …, 10, 30, 31]`，`costs = [2, 7, 15]` | `17` | 第 1 天买 30 天票管到第 30 天，第 31 天买 1 天票，15 + 2 = 17 |
+
+LeetCode 的范围是 `1 <= len(days) <= 365`，`1 <= costs[i] <= 1000`。
 
 [LeetCode 原题](https://leetcode.com/problems/minimum-cost-for-tickets/)
@@ -11,29 +18,102 @@
 ## 思路
 
-`dp[d]` 表示覆盖到第 d 天为止的最低花费。不出行的日子 `dp[d] = dp[d−1]`；出行的日子在三种票里选：今天买 1 天票 `dp[d−1] + c1`，或者 7 天前买的 7 天票 `dp[d−7] + c7`，或者 30 天票 `dp[d−30] + c30`（下标小于 0 当作 0）。
+用 `best[d]` 表示「第 1 天到第 d 天里的出行日全部有票」的最低花费，`best[0] = 0`。
+
+第 d 天不出行，不用为它花钱，`best[d] = best[d - 1]`。
+
+第 d 天出行，看管着第 d 天的那几张票里最晚结束的一张。先假设它就在第 d 天结束，本节最后一段说明为什么可以这样假设。一张时长为 `dur` 的票在第 d 天结束，管的是第 `d - dur + 1` 天到第 d 天，在第 `d - dur + 1` 天买。它管不到的是第 `d - dur` 天及以前，那部分的最低花费是 `best[d - dur]`。所以：
+
+```text
+best[d] = min(best[d - 1] + c1, best[d - 7] + c7, best[d - 30] + c30)
+```
+
+`d - dur` 小于 0 时按 0 算：票管到第 1 天以前也没关系，前面没有出行日要付钱。
+
+这个递推是对的，理由是任何一种买法都能调整成上面的形状而不变贵。某张票管着第 d 天、却在第 d 天之后才结束，把它整体往前挪到第 d 天结束，价格不变。它多出来的那几天在第 d 天之后，不属于「第 1 天到第 d 天」这个子问题。挪完以后，最后一张票在第 d 天结束，剩下的票要管住第 `d - dur` 天及以前的出行日，花费至少是 `best[d - dur]`。
+
+> [!say] Let best of d be the cheapest way to cover every travel day up to day d. On a non-travel day it just carries over from the day before. On a travel day, the last pass ends today, so I try a one-day, seven-day and thirty-day pass ending today, add the best cost for the days before that pass starts, and take the minimum.
 
 ## 代码
 
 ```python
-def mincost_tickets(days, costs):
-    day_set, last = set(days), days[-1]
-    dp = [0] * (last + 1)
-    for d in range(1, last + 1):
-        if d not in day_set:
-            dp[d] = dp[d - 1]
+from typing import List
+
+PASS_DURATIONS = (1, 7, 30)
+
+
+def mincost_tickets(days: List[int], costs: List[int]) -> int:
+    """Return the cheapest total price that covers every day in `days`.
+
+    days: strictly increasing travel days, each in 1..365.
+    costs: prices of the 1-day, 7-day and 30-day passes, in that order.
+    An empty `days` needs no ticket, so the answer is 0.
+    """
+    if not days:
+        return 0
+    travel_days = set(days)
+    last_day = days[-1]
+    # best[d] = cheapest cost to cover every travel day in 1..d; best[0] = 0.
+    best = [0] * (last_day + 1)
+    for day in range(1, last_day + 1):
+        if day not in travel_days:
+            best[day] = best[day - 1]
             continue
-        dp[d] = min(dp[d - 1] + costs[0],
-                    dp[max(0, d - 7)] + costs[1],
-                    dp[max(0, d - 30)] + costs[2])
-    return dp[last]
+        best[day] = min(
+            best[max(0, day - duration)] + price
+            for duration, price in zip(PASS_DURATIONS, costs)
+        )
+    return best[last_day]
 ```
 
-本机跑过官方例子。
+招聘方说代码写法也计分，这一版有这几处考虑：
+
+- 票的时长放在常量 `PASS_DURATIONS`，和 `costs` 用 `zip` 配对。题目改成别的时长，只改这一行。
+- `days` 转成集合 `travel_days`，判断「今天出不出行」是 O(1)。直接写 `day in days` 每次要扫一遍列表。
+- LeetCode 保证 `days` 非空，HackerRank 的题面不一定写。空列表不用买票，返回 0，写进 docstring。数组只开到 `last_day`，最后一个出行日以后的天不影响答案。
+
+2026-10-26 用 Python 3.13 实际跑过：
+
+- 两个例子分别得 11 和 17，空列表得 0。
+- 和暴力解对拍。暴力解从第一个没票的出行日起，三种票各试一次，递归到底取最小。2000 组随机输入（最后一天不超过 80，出行日最多 12 个，每种票价 1 到 30），结果全部一致。
+- 一年 365 天都出行、`costs = [2, 7, 15]` 时得 187，耗时不到 1 毫秒。
+- 两种错误写法和正确版本在同一组输入上的结果，见「易错点」。
 
 ## 复杂度
 
-O(最后一天)，最多 365。
+时间 `O(L)`，`L` 是最后一个出行日，最多 365。每天只比较三种票。额外空间 `O(L)`，存 `best` 数组和出行日集合。
 
-## 英文讲法
+## 易错点
 
-> [!say] dp of day d is the cheapest way to cover every travel day up to d; on a travel day I try ending a one-, seven- or thirty-day pass today and take the minimum.
+- **漏了 `max(0, …)`**。写成 `best[day - duration]`，下标为负时 Python 不报错，从列表末尾倒着取。`days = [10, 15, 20]`、`costs = [4, 7, 10]` 实测：暴力解和正确版本都给 10（第 10 天买一张 30 天票），漏写版给 11。原因是第 20 天算 30 天票时读到 `best[-10]`，列表长 21，实际读的是 `best[11] = 4`，应该读 `best[0] = 0`。最后一天不够 30 时还可能直接 IndexError，`days = [1, 4, 6, 7, 8, 20]` 就是这样。
+- **把 7 天票的起点差一位**。7 天票在第 d 天结束时管第 `d - 6` 到第 d 天，前面接的是 `best[d - 7]`。写成 `best[d - 6]`，这张票就只管第 `d - 5` 到第 d 天，第 `d - 6` 天明明在票内，却又被算进前面的花费里（这类差一见 [[p:me/python-pitfalls]] 的「边界和差一」）。`days = [1, 2, …, 7]`、`costs = [2, 7, 15]` 实测：正确版本给 7（一张 7 天票），差一版给 9，因为第 1 天又单独买了一张 2 元的 1 天票。
+
+## Follow-up
+
+### 【推断】出行日的数值很大、票种不止三种
+
+面经只说 OA 题不是原题，范围不知道。【推断】如果出行日能到 `10^9`，按天开的 `best` 数组就开不下，这是上面解法里唯一要改的地方。改成按出行日的下标做 DP：`best[i]` 表示前 `i` 个出行日都有票的最低花费。第 `i` 个出行日 `day` 由一张在当天结束、时长 `duration` 的票管着，这张票管不到的是 `day - duration` 及以前的出行日，用 `bisect_right` 在前 `i` 个出行日里数出有几个，就是接在前面的 `best` 下标。推导和按天的版本一样，只是跳过了不出行的日子。
+
+```python
+from bisect import bisect_right
+from typing import List, Sequence
+
+
+def min_cost_any_passes(days: List[int], durations: Sequence[int], prices: Sequence[int]) -> int:
+    """Cheapest cover for sorted, distinct `days`; needs at least one pass type."""
+    # best[i] = cheapest cost to cover the first i travel days (days[0..i-1]).
+    best = [0] * (len(days) + 1)
+    for i, day in enumerate(days):
+        # A pass ending on `day` covers day - duration + 1 .. day, so the
+        # travel days at or before day - duration still need their own tickets.
+        best[i + 1] = min(
+            best[bisect_right(days, day - duration, 0, i)] + price
+            for duration, price in zip(durations, prices)
+        )
+    return best[-1]
+```
+
+时间 `O(n · k · log n)`，`n` 是出行日个数，`k` 是票种数，和日子的数值大小无关。额外空间 `O(n)`。
+
+2026-10-26 实际跑过：原题两个例子得 11 和 17，空列表得 0。和上面的暴力解对拍 2000 组（票种 1 到 4 种，时长 1 到 40，一半输入的出行日在 1 到 `10^9` 之间），全部一致。`10^5` 个出行日、日子最大到 `10^9`、4 种票时两次耗时 130 到 140 毫秒。
+
+> [!say] If the day numbers can be huge, I index the DP by travel day instead of by calendar day, and a binary search tells me how many earlier travel days each pass cannot reach.
更新题目 983. Minimum Cost For Tickets

body

meta
