题目描述
思路解析动画文字版
记住这句口诀：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 母题。
参考代码
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]复杂度
- 时间：O(n)，每个出行日只对 3 种票各退一小段 j，票数是常数，总体线性
- 空间：O(n)，一维 dp 数组，长度 n+1
易错点
面试追问把动画讲成自己的话
追问这题和「跳跃 / 区间覆盖」类 DP 有什么共性？
追问如果票的种类不是固定三种、而是给一组任意 (天数, 价格)，怎么改？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最佳观光组合
LeetCode 1014 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题