983. 最低票价
题目描述
输入严格递增的数组 days，列出未来一年中你要出行的日子，每天用 1 到 365 的整数表示。另给长度为 3 的数组 costs。
通行证有三种：1 天票价格 costs[0]，7 天票价格 costs[1]，30 天票价格 costs[2]。从购买当天起算，在对应天数内可以不限次出行。例如第 2 天买的 7 天票覆盖第 2 天到第 8 天。
返回让 days 中每一天都被某张通行证覆盖的最低总花费。
示例 1
输入：days = [1,4,6,7,8,20], costs = [2,7,15] 输出：11
解释：第 1 天买 1 天票，第 3 天买 7 天票（覆盖 3 到 9），第 20 天买 1 天票，共 11。
示例 2
输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] 输出：17
解释：第 1 天买 30 天票覆盖到第 30 天，第 31 天再买 1 天票，共 17。
数据范围
1 <= days.length <= 3651 <= days[i] <= 365days严格递增。costs.length == 31 <= costs[i] <= 1000
解题思路：按日历天数 DP
设 dp[d] 为覆盖前 d 天里所有出行日的最小花费。第 d 天不出行，就不用为它买票，dp[d] = dp[d-1]。第 d 天出行，它必定被最后买的那张票覆盖：若是 1 天票，前面要覆盖到 d-1；若是 7 天票（最晚第 d-6 天买也能管到 d），前面只需覆盖到 d-7；30 天票同理。所以 dp[d] = min(dp[d-1]+c0, dp[d-7]+c1, dp[d-30]+c2)，下标小于 0 时按 0 算。
为什么正确
dp[d] 只依赖更小的下标，从小到大算时所需的值都已经是最优。
复杂度分析
时间 O(W)，空间 O(W)，W = days 的最后一天（≤ 365）。
易错点
贪心地“按单价最便宜的票买”不对，要看具体出行日的分布。另外 costs 不一定递增，可能 1 天票反而比 7 天票贵，三种都要比。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
last = days[-1]
travel = set(days)
dp = [0] * (last + 1)
for d in range(1, last + 1):
if d not in travel:
dp[d] = dp[d - 1]
continue
a = dp[d - 1] + costs[0]
b = dp[max(0, d - 7)] + costs[1]
c = dp[max(0, d - 30)] + costs[2]
dp[d] = min(a, b, c)
return dp[last]class Solution {
public int mincostTickets(int[] days, int[] costs) {
int last = days[days.length - 1];
boolean[] travel = new boolean[last + 1]; for (int d : days) travel[d] = true;
int[] dp = new int[last + 1];
for (int d = 1; d <= last; d++) {
if (!travel[d]) {
dp[d] = dp[d - 1];
continue;
}
int a = dp[d - 1] + costs[0];
int b = dp[Math.max(0, d - 7)] + costs[1];
int c = dp[Math.max(0, d - 30)] + costs[2];
dp[d] = Math.min(a, Math.min(b, c));
}
return dp[last];
}
}class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int last = days.back();
unordered_set<int> travel(days.begin(), days.end());
vector<int> dp(last + 1, 0);
for (int d = 1; d <= last; d++) {
if (!travel.count(d)) {
dp[d] = dp[d - 1];
continue;
}
int a = dp[d - 1] + costs[0];
int b = dp[max(0, d - 7)] + costs[1];
int c = dp[max(0, d - 30)] + costs[2];
dp[d] = min({a, b, c});
}
return dp[last];
}
};func mincostTickets(days []int, costs []int) int {
last := days[len(days)-1]
travel := make([]bool, last+1)
for _, d := range days { travel[d] = true }
dp := make([]int, last+1)
for d := 1; d <= last; d++ {
if !travel[d] {
dp[d] = dp[d-1]
continue
}
a := dp[d-1] + costs[0]
b := dp[max(0, d-7)] + costs[1]
c := dp[max(0, d-30)] + costs[2]
dp[d] = min(a, b, c)
}
return dp[last]
}var mincostTickets = function(days, costs) {
const last = days[days.length - 1];
const travel = new Set(days);
const dp = new Array(last + 1).fill(0);
for (let d = 1; d <= last; d++) {
if (!travel.has(d)) {
dp[d] = dp[d - 1];
continue;
}
const a = dp[d - 1] + costs[0];
const b = dp[Math.max(0, d - 7)] + costs[1];
const c = dp[Math.max(0, d - 30)] + costs[2];
dp[d] = Math.min(a, b, c);
}
return dp[last];
};function mincostTickets(days: number[], costs: number[]): number {
const last = days[days.length - 1];
const travel = new Set(days);
const dp = new Array(last + 1).fill(0);
for (let d = 1; d <= last; d++) {
if (!travel.has(d)) {
dp[d] = dp[d - 1];
continue;
}
const a = dp[d - 1] + costs[0];
const b = dp[Math.max(0, d - 7)] + costs[1];
const c = dp[Math.max(0, d - 30)] + costs[2];
dp[d] = Math.min(a, b, c);
}
return dp[last];
}其他解法
按天 DP 对日历上每一天都建状态，转移直接看 d-1、d-7、d-30；按旅行日 DP 只对真正出行的日子建状态，用指针找到票过期后的第一个旅行日，适合日期稀疏的情况。
解法 2：按旅行日下标 DP + 指针 时间 O(n)，空间 O(n)
dp[i] 表示从第 i 个旅行日开始，覆盖剩下所有旅行日的最小花费，从后往前计算。在第 i 天买时长为 1、7、30 的票，会覆盖所有 days[j] < days[i] + 时长 的旅行日，所以下一个要买票的位置就是第一个不被覆盖的下标 j。三种票的时长递增，j 只需向后移动，转移为 dp[i] = min(dp[j] + cost)。
状态数只和旅行日个数 n（不超过 365）有关，与日期范围无关，日期跨度很大时依然高效。需要多维护一个指针，不如按天 DP 直观。
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
n = len(days)
durations = (1, 7, 30)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
best = float('inf')
j = i
for cost, dur in zip(costs, durations):
while j < n and days[j] < days[i] + dur:
j += 1
best = min(best, dp[j] + cost)
dp[i] = best
return dp[0]class Solution {
public int mincostTickets(int[] days, int[] costs) {
int n = days.length;
int[] durations = {1, 7, 30};
int[] dp = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
int best = Integer.MAX_VALUE, j = i;
for (int t = 0; t < 3; t++) {
while (j < n && days[j] < days[i] + durations[t]) j++;
best = Math.min(best, dp[j] + costs[t]);
}
dp[i] = best;
}
return dp[0];
}
}class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int n = days.size();
int durations[3] = {1, 7, 30};
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
int best = INT_MAX, j = i;
for (int t = 0; t < 3; t++) {
while (j < n && days[j] < days[i] + durations[t]) j++;
best = min(best, dp[j] + costs[t]);
}
dp[i] = best;
}
return dp[0];
}
};func mincostTickets(days []int, costs []int) int {
n := len(days)
durations := []int{1, 7, 30}
dp := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
best, j := math.MaxInt32, i
for t := 0; t < 3; t++ {
for j < n && days[j] < days[i]+durations[t] {
j++
}
best = min(best, dp[j]+costs[t])
}
dp[i] = best
}
return dp[0]
}var mincostTickets = function(days, costs) {
const n = days.length;
const durations = [1, 7, 30];
const dp = new Array(n + 1).fill(0);
for (let i = n - 1; i >= 0; i--) {
let best = Infinity, j = i;
for (let t = 0; t < 3; t++) {
while (j < n && days[j] < days[i] + durations[t]) j++;
best = Math.min(best, dp[j] + costs[t]);
}
dp[i] = best;
}
return dp[0];
};function mincostTickets(days: number[], costs: number[]): number {
const n = days.length;
const durations = [1, 7, 30];
const dp = new Array<number>(n + 1).fill(0);
for (let i = n - 1; i >= 0; i--) {
let best = Infinity, j = i;
for (let t = 0; t < 3; t++) {
while (j < n && days[j] < days[i] + durations[t]) j++;
best = Math.min(best, dp[j] + costs[t]);
}
dp[i] = best;
}
return dp[0];
}