LeetCode 983. 最低票价

2025-12-09 HGNULB 约 10 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 983. 最低票价

题意分析

输入是一份升序的出行日期表和三种通行证价格：1 天、7 天、30 天。要求是买一组通行证，让每一个出行日都被至少一张通行证覆盖，并让总花费最小。

关键在于读懂通行证的覆盖语义：一张 7 天票在第 d 天启用，覆盖的是第 d 天到第 $d + 6$ 天，也就是连续 7 个自然日，而不是「7 个出行日」。这条语义直接决定了后面所有的下标该怎么写。

约束信号有三处很明确。第一，日期取值被限制在 1 到 365，规模小到可以对每一个自然日单独做决策，不必只在出行日之间跳跃。第二，days 严格递增且无重复，省掉了去重和排序。第三，通行证可以在任意一天启用，不要求必须在出行日启用，这意味着搜索空间比直觉更大，但也说明「让票尽量贴着出行日启用」不会更差。

边界上要留心：只有一个出行日、出行日全部集中在连续一周内、出行日稀疏地散落在一年里、以及最后一个出行日很小（比如只到第 2 天）导致回看的天数为负。

解法：按日期动态规划

核心思路

暴力做法是在每个出行日枚举「买哪种票」，然后递归到这张票覆盖结束后的下一个出行日。三种选择乘以出行日个数，最坏是 $O(3^n)$ 棵搜索树，n 到 365 时完全跑不动。

瓶颈在于同一个「已经覆盖到某一天，接下来怎么办」的子问题被不同的购票序列反复求解。比如先买 7 天票再买 1 天票、和先买两张 1 天票再买别的，都可能落到同一个后继位置上。

观察到子问题的全部信息只有一个数：目前已经付费覆盖到了第几天。至于这段覆盖是由哪几张票拼出来的、按什么顺序买的，对后面的决策完全没有影响。这就是一维状态足够的理由。

于是定义 dp 状态：dp[day] 表示让第 1 天到第 day 天之间所有出行日都被覆盖所需的最小花费，day 从 0 取到最后一个出行日 lastDay，边界是 $dp[0] = 0$。

转移分两种情况。第 day 天不出行时，这一天不需要任何票，$dp[day] = dp[day - 1]$。第 day 天出行时，一定存在一张覆盖了它的票，按这张票的种类分三类：如果是 1 天票，它只覆盖第 day 天本身，前面要靠 $dp[day - 1]$；如果是 7 天票，它最晚可以在第 $day - 6$ 天启用而仍然覆盖第 day 天，此时前面要靠 $dp[day - 7]$；30 天票同理对应 $dp[day - 30]$。取三者最小值即可，也就是
\[dp[day] = \min(dp[day-1] + costs[0],\ dp[day-7] + costs[1],\ dp[day-30] + costs[2])\]
这里天然带了一个贪心：既然要覆盖第 day 天，就让这张票尽可能晚启用，往前多覆盖的天数越多越好，所以 7 天票回看的是 day - 7 而不是 day - 1 到 day - 7 之间的某个中间值。回看下标可能为负，统一截断到 0，因为第 0 天之前没有任何出行日需要付费。

解题步骤

取 lastDay = days[days.length - 1]，只把 dp 算到这一天。之所以不必算满 365 天，是因为最后一个出行日之后不存在任何需要覆盖的日期，多算的部分只会原样继承。

开一个长度为 lastDay + 1 的布尔数组 travel，把每个出行日打上标记。这样后面判断「今天要不要出门」是 $O(1)$ 的，不需要在 days 里查找。

开长度同为 lastDay + 1 的 dp 数组，dp[0] 保持 0。多开这一位是为了让 day - 1、day - 7、day - 30 截断到 0 时有一个语义正确的落点。

从 day = 1 顺序推到 lastDay。顺序推进保证每次用到的三个回看位置都已经算好。

遇到非出行日直接 dp[day] = dp[day - 1]。这一步不是可有可无的优化：它让「回看到某个非出行日」时读到的仍然是那一天为止的真实最优花费，而不是 0。

遇到出行日就取三种票的最小值，回看下标用 max(0, day - k) 截断。截断到 0 表示这张票的覆盖范围已经把开头全部包住，前面不需要再花钱。

返回 dp[lastDay]，它就是覆盖全部出行日的最小花费。

以 days = [1, 4, 6, 7, 8, 20]、costs = [2, 7, 15] 走一遍：lastDay = 20，travel 在下标 1、4、6、7、8、20 上为真，dp[0] = 0。

第 1 天出行，三个候选是 $dp[0] + 2 = 2$、$dp[0] + 7 = 7$、$dp[0] + 15 = 15$，取最小得 dp[1] = 2。第 2、3 天不出行，直接继承成 dp[2] = 2、dp[3] = 2。第 4 天出行，候选是 $dp[3] + 2 = 4$、$dp[0] + 7 = 7$、$dp[0] + 15 = 15$，得 dp[4] = 4。第 5 天继承得 dp[5] = 4。第 6 天出行，候选是 $dp[5] + 2 = 6$、$dp[0] + 7 = 7$、$dp[0] + 15 = 15$，得 dp[6] = 6。

第 7 天出行，候选是 $dp[6] + 2 = 8$、$dp[0] + 7 = 7$、$dp[0] + 15 = 15$，7 天票第一次胜出，得 dp[7] = 7。第 8 天出行，候选是 $dp[7] + 2 = 9$、$dp[1] + 7 = 2 + 7 = 9$、$dp[0] + 15 = 15$，得 dp[8] = 9。

第 9 到第 19 天全部不出行，一路继承成 dp[19] = 9。第 20 天出行，候选是 $dp[19] + 2 = 11$、$dp[13] + 7 = 9 + 7 = 16$、$dp[0] + 15 = 15$，得 dp[20] = 11。返回 11，对应的方案正是第 1 天和第 4 天各买一张 1 天票、第 6 天买一张 7 天票覆盖第 6 到第 12 天、第 20 天再买一张 1 天票。

代码实现

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1];
        boolean[] travel = new boolean[lastDay + 1];
        for (int day : days) {
            travel[day] = true;
        }

        int[] dp = new int[lastDay + 1];
        for (int day = 1; day <= lastDay; day++) {
            if (!travel[day]) {
                dp[day] = dp[day - 1];
                continue;
            }
            int cost1 = dp[Math.max(0, day - 1)] + costs[0];
            int cost7 = dp[Math.max(0, day - 7)] + costs[1];
            int cost30 = dp[Math.max(0, day - 30)] + costs[2];
            dp[day] = Math.min(cost1, Math.min(cost7, cost30));
        }
        return dp[lastDay];
    }
}

func mincostTickets(days []int, costs []int) int {
    lastDay := days[len(days)-1]
    travel := make([]bool, lastDay+1)
    for _, day := range days {
        travel[day] = true
    }

    dp := make([]int, lastDay+1)
    for day := 1; day <= lastDay; day++ {
        if !travel[day] {
            dp[day] = dp[day-1]
            continue
        }
        cost1 := dp[maxInt(0, day-1)] + costs[0]
        cost7 := dp[maxInt(0, day-7)] + costs[1]
        cost30 := dp[maxInt(0, day-30)] + costs[2]
        dp[day] = minInt(cost1, minInt(cost7, cost30))
    }
    return dp[lastDay]
}

func minInt(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(D)$，$D$ 是最后一个出行日的编号，题目限定不超过 365。外层只有一趟从 1 到 D 的循环，每一天内部固定做三次加法和两次取最小，都是常数操作，标记 travel 的预处理是 $O(n)$，被 $O(D)$ 吸收。

空间复杂度：$O(D)$，dp 和 travel 各占一条长度 D + 1 的数组。由于回看距离最远是 30，理论上可以只保留最近 31 天的滚动窗口把空间压到 $O(1)$，但常数天数下没有实际收益。

关键点总结

状态该按「自然日」还是按「出行日下标」建，是这题真正的分水岭。按自然日建，转移下标就是简单的 day - 1、day - 7、day - 30；按出行日建则要二分查找「第一个大于等于 days[i] - 6 的出行日」，边界极易写错。当值域本身很小时，直接把值域当状态空间是最省心的选择。

「枚举最后一步」是线性 dp 的通用拆解手法。这里不去想整套购票方案，只问「覆盖住今天的那张票是哪种」，三种可能穷尽了所有情况，问题立刻塌缩成三个更小的同类问题。

贪心与 dp 在这题里是配合关系：dp 负责全局最优，贪心只用在「这张票尽量晚启用」这个局部判断上，并且它的正确性来自花费与启用时刻无关这一事实。把两者的分工讲清楚，比笼统说一句「这是 dp 题」更能体现理解深度。

非出行日的继承不是省事的写法，而是保证回看语义正确的必要一步。少了它，dp[day - 7] 读到的可能是一个从未被赋值的 0，整条链就断了。

面试视角：面试官常见的两个追问是「票的种类从三种变成 k 种怎么办」和「日期范围放大到 $10^9$ 怎么办」。前者答复杂度变成 $O(Dk)$，转移里换成对 k 种时长取最小；后者答值域不能再当状态，要改回按出行日下标做 dp 并用二分定位回看位置，复杂度是 $O(n \log n)$。

面试视角：写完后主动补一句「dp 数组单调不降，所以答案一定在 dp[lastDay] 而不需要全局取最小」，能说明你验证过状态的性质而不是照着模板抄。

易错点总结

错误写法：把 7 天票的回看位置写成 dp[day - 6]，误以为「覆盖 7 天」等于「往前推 6 天」。用例 days = [1, 2, 3, 4, 5, 6, 7]、costs = [2, 7, 15] → 第 7 天的 7 天票候选变成 $dp[1] + 7 = 9$，而正确的候选是 $dp[0] + 7 = 7$，最终返回 9，而正确答案是买一张 7 天票花 7。

错误写法：非出行日不做继承，任由 dp[day] 保持初始的 0。用例 days = [1, 4, 6, 7, 8, 20]、costs = [2, 7, 15] → dp[3] 停在 0，第 4 天算出 $dp[3] + 2 = 2$，第 1 天买的票被凭空抹掉，链式传播下去 dp[19] 也是 0，最终返回 2 而不是 11。

错误写法：数组长度开成 lastDay 而不是 lastDay + 1。用例 days = [1, 4, 6, 7, 8, 20] → 给 travel[20] 赋值时下标等于数组长度，直接抛出越界异常。

错误写法：回看下标不做非负截断，直接写 dp[day - 30]。用例 days = [1, 4, 6, 7, 8, 20] → 第 1 天就要读 dp[-29]，数组越界崩溃。

错误写法：把 30 天票的回看位置写成 dp[day - 29]。用例第 1 天到第 30 天全部出行、costs = [2, 7, 15] → 第 30 天的 30 天票候选变成 $dp[1] + 15 = 17$，而正确候选是 $dp[0] + 15 = 15$，最终返回 17 而不是 15。

错误写法：认为 30 天票在大多数数据下不划算而只比较 1 天票和 7 天票。用例第 1 天到第 30 天全部出行、costs = [2, 7, 15] → 只能靠 1 天票和 7 天票拼，算出来是 32，而买一张 30 天票只要 15。

错误写法：结尾遍历整个 dp 数组取最小值返回。用例 days = [1, 4, 6, 7, 8, 20]、costs = [2, 7, 15] → dp 单调不降，全局最小值是 dp[0] = 0，函数返回 0。

错误写法：把整个 dp 数组初始化成一个极大值当作「未计算」标记，却忘了把 dp[0] 重置回 0。用例 days = [1, 4, 6, 7, 8, 20]、costs = [2, 7, 15] → 第 1 天算 $dp[0] + 2$ 时整型加法溢出成负数，后续所有状态都被污染，返回一个负的花费。

相似题目

题目	难度	考察点
322. 零钱兑换	中等	面额种类不固定，转移要对整个硬币数组取最小
746. 使用最小花费爬楼梯	简单	转移只回看两格，是同类线性 dp 的最简形态
91. 解码方法	中等	求方案数而非最小值，回看长度取决于子串是否合法
198. 打家劫舍	中等	约束是相邻互斥，转移来自「选或不选」而非覆盖区间