LeetCode 983. 最低票价

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 腾讯 字节
标签
数组 动态规划

题目描述

✅ 983. 最低票价

image-20260929000647956

image-20260929000647962

题意分析

用有效期为 1、7、30 个连续自然日的通行证，覆盖 days 中的全部出行日期，求最低总费用。有效期按日期计算，不按出行次数计算；days 严格递增，所以最后一个元素就是需要处理的最后一天。

解法：按日期动态规划

核心思路

[!blue]

定义 dp[d] 为覆盖第 1 天到第 d 天之间所有出行需求的最低费用。它只描述“此前的出行都已覆盖”，不要求某张票恰好在当天到期，也不要求没有出行的日期必须有票。初始化 dp[0] = 0，表示还没有任何出行需求。

如果第 d 天不出行，需求与截至前一天完全相同，所以 dp[d] = dp[d - 1]。不能把这一项留为零，否则后续转移会丢掉此前已经需要的费用。

如果第 d 天出行，必然有一张票覆盖它。枚举这张票的有效期 t，让它覆盖截至当天的最后 t 天，即 [d - t + 1, d]，此前的需求由 dp[d - t] 负责。这不是强制实际方案在固定日期购票：任意覆盖当天的 t 天票，其起点都不早于 d - t + 1；将它前移至这个起点，不会丢失它原本覆盖的、截至第 d 天的任何需求，价格也不变。因此只考虑这种贴齐当天的覆盖区间就不会漏掉最优方案。

若 d - t < 0，此前已经没有需要处理的日期，统一使用 dp[0]。实际从第 1 天启用这张票即可覆盖到第 d 天，不需要在零日或负数日期购票。

所以出行日的三个候选分别是 dp[d - 1] + costs[0]、dp[max(0, d - 7)] + costs[1]、dp[max(0, d - 30)] + costs[2]，取最小值。每个候选都由一个已最优覆盖的前缀加一张合法通行证构成，而三种票已穷尽覆盖当天的选择，故得到的也是最优费用。

解题步骤

  1. 取最后一个出行日为 lastDay，用 travel 标记哪些自然日需要出行。
  2. 建立 dp[0..lastDay]，从第 1 天向后递推，保证所依赖的更早日期已经算好。
  3. 非出行日直接继承 dp[day - 1]。
  4. 出行日分别回看 1、7、30 天之前的状态，加上对应票价；早于零的下标截到零，三者取最小。
  5. 返回 dp[lastDay]，它覆盖了所有给定的出行日期。

代码实现

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 是最后出行日。标记出行日后，每个自然日只比较三个候选；日期互异且位于 1..D，出行日数量也不超过 D。
  • 空间复杂度：$O(D)$，用于出行标记和费用数组。

关键点总结

[!green]

  • 状态记录已覆盖的出行需求，非出行日不会让历史费用消失。
  • t 天票覆盖 [d - t + 1, d]，剩余前缀截止到 d - t。
  • 按票的覆盖长度回看旧状态，再加票价，而不是凭单日均价贪心选票。

易错点总结

[!yellow]

  • 七日票应回看 d - 7，不是 d - 6；后者会把已经纳入本张票覆盖范围的一天再次要求前缀处理。
  • 回看下标小于零时必须使用 dp[0]，否则在较早的出行日就会越界。
  • 非出行日也要写入上一天的费用，不能保留数组默认零值。
  • 票价不保证按有效期递增，必须比较三种完整费用，不能固定优先购买长票。

相似题目

题目 难度 关联与区别
322. 零钱兑换 中等 同样最小化累计费用，但本题每次购买覆盖一段日期，状态应按出行位置或时间推进。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/85625139
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！