§1

题目描述

给升序的出行日 days 和价格 costs（依次对应 1 天 / 7 天 / 30 天通票）。每张票从某天买入、覆盖连续若干天。求覆盖所有出行日的最低总花费。

输入 = days=[1,4,6,7,8,20], costs=[2,7,15]　输出 = 11　（两张 1 天票 + 一张 7 天票）

§2

思路解析

一句话答案：LeetCode 983 最低票价：按出行日做动态规划，dp[i] 记办妥前 i 个出行日的最低花费，每格枚举 1、7、30 天票、接上票管不到那段的 dp 取最小。时间 O(n)、空间 O(n)。

最低票价这道题到底要我们决定什么

给升序的出行日 days 和三种票价 costs（1 天、7 天、30 天通票），每张票从买入当天起连续覆盖若干天，求盖住所有出行日的最低总花费。示例 days=[1,4,6,7,8,20]、costs=[2,7,15]，答案 11：一张 7 天票罩住 1 到 7 号，8 号、20 号再各买一张 1 天票。难点是每个出行日都能挑三种票、长票还跨盖多个出行日。

为什么把每天买什么票都试一遍会算不过来

每个出行日都能挑 1、7、30 天三种票，n 个出行日就有 3ⁿ 种买法，几十个已是天文数字。何况长票跨盖多个出行日，硬枚举里「前面怎么办」被反复重算。既然「办妥前若干个出行日的最低花费」问一次就定死，算一次存起来复用，指数枚举就压成一条线。

状态为什么定成『办妥前 i 个出行日』、还按出行日而不是日历天推

动态规划（DP，办妥前 i 个出行日的最低花费只算一次存 dp[i]、直接复用）在这里把状态定成 dp[i]（i 是出行日个数，不是日历第几天），dp[0]=0 是没出行日、不花钱的地基。盯出行日是因为没出行的日子不用买票，排进表全是白算的空格；答案就是最后一格 dp[n]。

三种票各往回望 1、7、30 天，怎么接上更早那段的 dp

填 dp[i] 只盯第 i 个出行日，记它日期为 today。d 天票含当天共 d 天，覆盖起点是 today-d+1：1 天票只盖当天，7 天票往回盖到 today-7+1，30 天票盖到 today-30+1。这张票罩住 today 往前一截出行日，剩下更早、它够不着的又是一个子问题：管不到的是前 j+1 个出行日（j 是往回退时停在的那个出行日的下标），那段花费就是 dp[j+1]，接上再加票价 c。三种票取最小：dp[i]=min(三种票的 dp[j+1]+c)。往回退 j，就是往前跳过被这张票盖住的出行日、落到第一个没盖住的。

拿 days=[1,4,6,7,8,20] 把这张表一格格填出来

dp[0]=0 打底。1 号：1 天票 dp[0]+2=2 最省，dp[1]=2。4 号：dp[1]+2=4，dp[2]=4。6 号：dp[2]+2=6，dp[3]=6。到 7 号才有看头：1 天票 dp[3]+2=8，可 7 天票从 7 号往回盖到 1 号、把 1、4、6、7 号全罩住，接 dp[0]+7=7 更便宜，dp[4]=7。8 号：dp[4]+2=9，dp[5]=9。20 号离得远，7 天票只盖到 14 号、30 天票加 15 都不划算，1 天票 dp[5]+2=11，dp[6]=11 就是答案。

覆盖起点写成 today-d 少个 +1，整张表为什么会悄悄接错

覆盖起点是 today-d+1；漏掉 +1 写成 today-d 就把覆盖多算一天，往回退 j 时跳掉本该保留的出行日，dp 接错子问题、答案偏小；退 j 的条件 days[j] >= today-d+1 里那个 +1 正是防它。复杂度每个出行日只对 3 种票各退一小段 j，票数是常数，时间 O(n)（大 O 记号，描述规模变大时操作数怎么涨）、空间 O(n)。两处边界也别弄错：只有一个出行日也得把三种票比一遍取最小；密集连续多日要让一张长票和多张短票正面比价。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

记住这句口诀：dp[i] = 三种票里挑最便宜的「这张票的钱 + 这张票管不到的那段的 dp」。下面每填一格都在套它。

dp 表第 0 格固定是 0：还没安排任何出行日，自然花费为 0。绿色这一格是后面所有计算的地基。

给第 1 个出行日（1 号）试买 1 天票：它能往回覆盖到 1 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 2 = 2 元。目前最便宜，暂记为候选 2。

给第 1 个出行日（1 号）试买 7 天票：它能往回覆盖到 -5 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。比当前候选 2 贵，不采用。

给第 1 个出行日（1 号）试买 30 天票：它能往回覆盖到 -28 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 2 贵，不采用。

第 1 个出行日结算：三种票比下来最便宜的是 1 天票，dp[1] = 2（绿色锁定）。后面更晚的出行日会接着用它。

给第 2 个出行日（4 号）试买 1 天票：它能往回覆盖到 4 号。更早的日子交给 dp[1]（蓝色，=2）。这条方案花 2 + 2 = 4 元。目前最便宜，暂记为候选 4。

给第 2 个出行日（4 号）试买 7 天票：它能往回覆盖到 -2 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。比当前候选 4 贵，不采用。

给第 2 个出行日（4 号）试买 30 天票：它能往回覆盖到 -25 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 4 贵，不采用。

第 2 个出行日结算：三种票比下来最便宜的是 1 天票，dp[2] = 4（绿色锁定）。后面更晚的出行日会接着用它。

给第 3 个出行日（6 号）试买 1 天票：它能往回覆盖到 6 号。更早的日子交给 dp[2]（蓝色，=4）。这条方案花 4 + 2 = 6 元。目前最便宜，暂记为候选 6。

给第 3 个出行日（6 号）试买 7 天票：它能往回覆盖到 0 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。比当前候选 6 贵，不采用。

给第 3 个出行日（6 号）试买 30 天票：它能往回覆盖到 -23 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 6 贵，不采用。

第 3 个出行日结算：三种票比下来最便宜的是 1 天票，dp[3] = 6（绿色锁定）。后面更晚的出行日会接着用它。

给第 4 个出行日（7 号）试买 1 天票：它能往回覆盖到 7 号。更早的日子交给 dp[3]（蓝色，=6）。这条方案花 6 + 2 = 8 元。目前最便宜，暂记为候选 8。

给第 4 个出行日（7 号）试买 7 天票：它能往回覆盖到 1 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。目前最便宜，暂记为候选 7。

给第 4 个出行日（7 号）试买 30 天票：它能往回覆盖到 -22 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 7 贵，不采用。

第 4 个出行日结算：三种票比下来最便宜的是 7 天票，dp[4] = 7（绿色锁定）。后面更晚的出行日会接着用它。

给第 5 个出行日（8 号）试买 1 天票：它能往回覆盖到 8 号。更早的日子交给 dp[4]（蓝色，=7）。这条方案花 7 + 2 = 9 元。目前最便宜，暂记为候选 9。

给第 5 个出行日（8 号）试买 7 天票：它能往回覆盖到 2 号。更早的日子交给 dp[1]（蓝色，=2）。这条方案花 2 + 7 = 9 元。与当前候选 9 打平；本轮按演示保留先到的候选 9。

给第 5 个出行日（8 号）试买 30 天票：它能往回覆盖到 -21 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 9 贵，不采用。

第 5 个出行日结算：1 天票和 7 天票都做到 9 元、并列最省，本轮按演示保留先到的 1 天票，dp[5] = 9（绿色锁定）。后面更晚的出行日会接着用它。

给第 6 个出行日（20 号）试买 1 天票：它能往回覆盖到 20 号。更早的日子交给 dp[5]（蓝色，=9）。这条方案花 9 + 2 = 11 元。目前最便宜，暂记为候选 11。

给第 6 个出行日（20 号）试买 7 天票：它能往回覆盖到 14 号。更早的日子交给 dp[5]（蓝色，=9）。这条方案花 9 + 7 = 16 元。比当前候选 11 贵，不采用。

给第 6 个出行日（20 号）试买 30 天票：它能往回覆盖到 -9 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 11 贵，不采用。

第 6 个出行日结算：三种票比下来最便宜的是 1 天票，dp[6] = 11（绿色锁定）。后面更晚的出行日会接着用它。

表填满，最右一格 dp[6] = 11 就是覆盖全部出行日的最低费用。回看锁定的路径：在第 4 个出行日（7 号）这格用一张 7 天票接 dp[0]，它从 1 号起覆盖 1 到 7 号，把出行日 1、4、6、7 全包了；接着 8 号买 1 张 1 天票（dp[5]），20 号再买 1 张 1 天票（dp[6]）。合计 7 + 2 + 2 = 11 元。

边界先想清：单日也要把三种票比一遍取最小（本例 1 天票最省）；密集的连续多日要比「多张短票 vs 一张长票」哪个更划算。

两个追问，核心是认出「枚举最后一步 + 接子问题」这个可推广的 DP 母题。

§3

参考代码

from typing import Listclass Solution:    def mincostTickets(self, days: List[int], costs: List[int]) -> int:        durations = [1, 7, 30]        n = len(days)        dp = [0] * (n + 1)        for i in range(1, n + 1):            dp[i] = 10**9            for d, c in zip(durations, costs):                j = i - 1                while j >= 0 and days[j] >= days[i-1] - d + 1:                    j -= 1                dp[i] = min(dp[i], dp[j + 1] + c)        return dp[n]

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n)，每个出行日只对 3 种票各退一小段 j，票数是常数，总体线性
空间：O(n)，一维 dp 数组，长度 n+1

§5

易错点

✗ 错误写法：dp 按日历天数（1..365）建表

✓ 正确写法：dp 只按「出行日」建表，长度 n+1

没出行的日子不必决策，按出行日建表更省、下标也更清晰

✗ 错误写法：while 退 j 的条件写成 days[j] ≥ today - d

✓ 正确写法：条件是 days[j] ≥ today - d + 1

d 天票从买入当天起含当天共罩 d 天，最早只到 today - d + 1；写成 ≥ today - d 会把更早一天也当成被覆盖，多退一格、覆盖范围虚增一天

✗ 错误写法：dp 初值设 0

✓ 正确写法：dp[0]=0、其余先当无穷大再取 min

初值 0 会让「还没算的格子」被误当成花费为 0 的合法方案，污染 min

面试追问把动画讲成自己的话

追问这题和「跳跃 / 区间覆盖」类 DP 有什么共性？

都是「枚举最后一步的选择，把序列切成一段当前选择 + 一段子问题」。这里的「最后一步」是覆盖到末尾出行日的那张票，切完往前接 dp[j+1]。认出这个母题，凑零钱、跳台阶、单词拆分都能套同一套「枚举最后一步」的思路。

追问如果票的种类不是固定三种、而是给一组任意 (天数, 价格)，怎么改？

把内层固定的三种票换成遍历这组票即可，转移方程不变。但要留意复杂度：现在每张票仍用朴素 while 往前退找覆盖边界，票期任意变长时一次回退最坏可到 O(n)，于是总复杂度退化成 O(票种数 × n²)。想压回接近 O(票种数 × n)，可为每种票各维护一个单调推进的指针，或对每张票用二分定位第一个未被覆盖的下标。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 动态规划套路 52/108

最佳观光组合

LeetCode 1014 · 中等 · 沿着动态规划套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from typing import Listclass Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: durations = [1, 7, 30] n = len(days) dp = [0] * (n + 1) for i in range(1, n + 1): dp[i] = 10**9 for d, c in zip(durations, costs): j = i - 1 while j >= 0 and days[j] >= days[i-1] - d + 1: j -= 1 dp[i] = min(dp[i], dp[j + 1] + c) return dp[n]