LeetCode 983中等DP
最低票价 图解题解
这道题到底在问什么
给升序的出行日 days 和价格 costs（依次对应 1 天 / 7 天 / 30 天通票）。每张票从某天买入、覆盖连续若干天。求覆盖所有出行日的最低总花费。
- 输入
- days=[1,4,6,7,8,20], costs=[2,7,15]
- 输出
- 11 （两张 1 天票 + 一张 7 天票）
最优解：一步一步想明白
- 3记住这句口诀：dp[i] = 三种票里挑最便宜的「这张票的钱 + 这张票管不到的那段的 dp」。下面每填一格都在套它。
- 4dp 表第 0 格固定是 0：还没安排任何出行日，自然花费为 0。绿色这一格是后面所有计算的地基。
- 5给第 1 个出行日（1 号）试买 1 天票：它能往回覆盖到 1 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 2 = 2 元。目前最便宜，暂记为候选 2。
- 6给第 1 个出行日（1 号）试买 7 天票：它能往回覆盖到 -5 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。比当前候选 2 贵，不采用。
- 7给第 1 个出行日（1 号）试买 30 天票：它能往回覆盖到 -28 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 2 贵，不采用。
- 8第 1 个出行日结算：三种票比下来最便宜的是 1 天票，dp[1] = 2（绿色锁定）。后面更晚的出行日会接着用它。
- 9给第 2 个出行日（4 号）试买 1 天票：它能往回覆盖到 4 号。更早的日子交给 dp[1]（蓝色，=2）。这条方案花 2 + 2 = 4 元。目前最便宜，暂记为候选 4。
- 10给第 2 个出行日（4 号）试买 7 天票：它能往回覆盖到 -2 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。比当前候选 4 贵，不采用。
- 11给第 2 个出行日（4 号）试买 30 天票：它能往回覆盖到 -25 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 4 贵，不采用。
- 12第 2 个出行日结算：三种票比下来最便宜的是 1 天票，dp[2] = 4（绿色锁定）。后面更晚的出行日会接着用它。
- 13给第 3 个出行日（6 号）试买 1 天票：它能往回覆盖到 6 号。更早的日子交给 dp[2]（蓝色，=4）。这条方案花 4 + 2 = 6 元。目前最便宜，暂记为候选 6。
- 14给第 3 个出行日（6 号）试买 7 天票：它能往回覆盖到 0 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。比当前候选 6 贵，不采用。
- 15给第 3 个出行日（6 号）试买 30 天票：它能往回覆盖到 -23 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 6 贵，不采用。
- 16第 3 个出行日结算：三种票比下来最便宜的是 1 天票，dp[3] = 6（绿色锁定）。后面更晚的出行日会接着用它。
- 17给第 4 个出行日（7 号）试买 1 天票：它能往回覆盖到 7 号。更早的日子交给 dp[3]（蓝色，=6）。这条方案花 6 + 2 = 8 元。目前最便宜，暂记为候选 8。
- 18给第 4 个出行日（7 号）试买 7 天票：它能往回覆盖到 1 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 7 = 7 元。目前最便宜，暂记为候选 7。
- 19给第 4 个出行日（7 号）试买 30 天票：它能往回覆盖到 -22 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 7 贵，不采用。
- 20第 4 个出行日结算：三种票比下来最便宜的是 7 天票，dp[4] = 7（绿色锁定）。后面更晚的出行日会接着用它。
- 21给第 5 个出行日（8 号）试买 1 天票：它能往回覆盖到 8 号。更早的日子交给 dp[4]（蓝色，=7）。这条方案花 7 + 2 = 9 元。目前最便宜，暂记为候选 9。
- 22给第 5 个出行日（8 号）试买 7 天票：它能往回覆盖到 2 号。更早的日子交给 dp[1]（蓝色，=2）。这条方案花 2 + 7 = 9 元。与当前候选 9 打平；本轮按演示保留先到的候选 9。
- 23给第 5 个出行日（8 号）试买 30 天票：它能往回覆盖到 -21 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 9 贵，不采用。
- 24第 5 个出行日结算：1 天票 和 7 天票 都做到 9 元、并列最省，本轮按演示保留先到的 1 天票，dp[5] = 9（绿色锁定）。后面更晚的出行日会接着用它。
- 25给第 6 个出行日（20 号）试买 1 天票：它能往回覆盖到 20 号。更早的日子交给 dp[5]（蓝色，=9）。这条方案花 9 + 2 = 11 元。目前最便宜，暂记为候选 11。
- 26给第 6 个出行日（20 号）试买 7 天票：它能往回覆盖到 14 号。更早的日子交给 dp[5]（蓝色，=9）。这条方案花 9 + 7 = 16 元。比当前候选 11 贵，不采用。
- 27给第 6 个出行日（20 号）试买 30 天票：它能往回覆盖到 -9 号。更早的日子交给 dp[0]（蓝色，=0）。这条方案花 0 + 15 = 15 元。比当前候选 11 贵，不采用。
- 28第 6 个出行日结算：三种票比下来最便宜的是 1 天票，dp[6] = 11（绿色锁定）。后面更晚的出行日会接着用它。
- 29表填满，最右一格 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 元。
⚠️ 容易写错的地方
✗ 错：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
完整代码（Python / C++ / Java）
Python
from typing import List
class 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]C++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
vector<int> dur = {1,7,30};
int n = days.size();
vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i) {
dp[i] = 1000000000;
for (int t = 0; t < 3; ++t) {
int j = i - 1;
while (j >= 0 && days[j] >= days[i-1] - dur[t] + 1) j--;
dp[i] = min(dp[i], dp[j + 1] + costs[t]);
}
}
return dp[n];
}
};Java
import java.util.*;
class Solution {
public int mincostTickets(int[] days, int[] costs) {
int[] dur = {1, 7, 30};
int n = days.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = 1_000_000_000;
for (int t = 0; t < 3; t++) {
int j = i - 1;
while (j >= 0 && days[j] >= days[i - 1] - dur[t] + 1) j--;
dp[i] = Math.min(dp[i], dp[j + 1] + costs[t]);
}
}
return dp[n];
}
}复杂度
时间
O(n)
每个出行日只对 3 种票各退一小段 j，票数是常数，总体线性
空间
O(n)
一维 dp 数组，长度 n+1
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最低票价 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题和「跳跃 / 区间覆盖」类 DP 有什么共性？+
都是「枚举最后一步的选择，把序列切成一段当前选择 + 一段子问题」。这里的「最后一步」是覆盖到末尾出行日的那张票，切完往前接 dp[j+1]。认出这个母题，凑零钱、跳台阶、单词拆分都能套同一套「枚举最后一步」的思路。
如果票的种类不是固定三种、而是给一组任意 (天数, 价格)，怎么改？+
把内层固定的三种票换成遍历这组票即可，转移方程不变。但要留意复杂度：现在每张票仍用朴素 while 往前退找覆盖边界，票期任意变长时一次回退最坏可到 O(n)，于是总复杂度退化成 O(票种数 × n²)。想压回接近 O(票种数 × n)，可为每种票各维护一个单调推进的指针，或对每张票用二分定位第一个未被覆盖的下标。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最低票价 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。