983. 最低票价

发表于 2026-01-06 分类于力扣阅读次数： Waline：本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

贪心
双指针
线性DP

思路

一、问题抽象

给定一个严格递增的数组 \[ days = [d_1, d_2, \dots, d_n] \] 表示需要出行的日期；以及三种通行证的费用：

1 天票，费用 \(c_1\)
7 天票，费用 \(c_7\)
30 天票，费用 \(c_{30}\)

目标是在覆盖所有出行日期的前提下，使总费用最小。

二、未优化版本：逆序动态规划

1. 状态定义

定义状态： \[ f[i] = \text{覆盖从第 } i \text{ 个出行日到最后一个出行日的最小费用} \] 其中：

出行日下标从 1 开始
边界条件为：

\[ f[n+1] = 0 \]

表示当已经没有出行日需要覆盖时，费用为 0。

2. 状态转移方程

考虑在第 \(i\) 个出行日（日期 \(days[i]\)）购买一张通行证。

若购买一张有效期为 \(d\) 天的通行证（\(d \in \{1,7,30\}\)）：

该通行证将覆盖所有满足

\[ days[j] - days[i] + 1 \le d \]

的出行日

设 \(j\) 为第一个 不被该通行证覆盖 的出行日下标

则状态转移为： \[ f[i] = \min_{d \in \{1,7,30\}} \left( f[j] + cost(d) \right) \]

3. 未优化代码（逆序 + 暴力查找）

class Solution {
public:
    static const int maxn = 4e2 + 5;
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int d[3] = {1, 7, 30};
        int n = days.size();
        int f[maxn];

        // 边界：没有出行日需要覆盖
        f[n + 1] = 0;

        // 从后向前 DP
        for (int i = n; i >= 1; --i) {
            f[i] = INT_MAX >> 1;
            for (int k = 0; k < 3; ++k) {
                int j = i + 1;
                // 找到第一个不被当前通行证覆盖的出行日
                while (j <= n && days[j - 1] - days[i - 1] + 1 <= d[k])
                    ++j;
                f[i] = min(f[i], f[j] + costs[k]);
            }
        }
        return f[1];
    }
};

4. 时间复杂度

状态数：\(O(n)\)
每个状态中通过 while 寻找下一个位置，最坏 \(O(n)\)

总体复杂度： \[ O(n^2) \]

三、关键性质：`f` 数组的单调性

1. 单调性结论（逆序）

对于逆序 DP 定义的 \(f[i]\)，有： \[ f[1] \ge f[2] \ge \dots \ge f[n] \ge f[n+1] = 0 \]

2. 证明

\(f[i]\) 表示覆盖出行日集合 \([i,n]\) 的最小费用
\(f[i+1]\) 表示覆盖集合 \([i+1,n]\)

显然： \[ [i+1,n] \subseteq [i,n] \] 覆盖更少的出行日不可能需要更高的最小费用，因此： \[ f[i] \ge f[i+1] \]

3. 单调性带来的重要结论

当购买一张 7 天 / 30 天通行证 时：

若该通行证从第 \(i\) 个出行日开始
它能够覆盖的出行日区间是一个 连续区间
覆盖越多出行日，剩余需要覆盖的集合越小
由于 \(f\) 是单调不增的，覆盖得越多，对应的 \(f[\text{next}]\) 越小

因此：

对于固定的一种通行证，最优方案一定是 让它覆盖尽可能多的出行日

这意味着：对于每种通行证，只需要关心一个确定的边界位置，而不需要在一段区间内取最小值。

这正是可以使用 双指针优化 的根本原因。

四、倒序 DP 的双指针优化

1. 思路说明

在逆序 DP 中：

当 \(i\) 从 \(n\) 向 \(1\) 移动时
对于 7 天、30 天通行证，其“最远可覆盖位置”只会向左移动

因此可以维护两个指针：

j：7 天通行证的最远覆盖下标
k：30 天通行证的最远覆盖下标

二者都具有 单调性，每个指针最多移动 \(n\) 次。

2. 倒序双指针优化代码

class Solution {
public:
    static const int maxn = 4e2 + 5;
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        int f[maxn];

        // 边界条件
        f[n + 1] = 0;

        // j, k 分别表示 7 天 / 30 天通行证的最远覆盖下标
        int j = n, k = n;

        for (int i = n; i >= 1; --i) {
            // 购买 1 天票
            f[i] = f[i + 1] + costs[0];

            // 调整 7 天票的覆盖边界
            while (j >= 1 && days[j - 1] - days[i - 1] + 1 > 7)
                --j;

            // 调整 30 天票的覆盖边界
            while (k >= 1 && days[k - 1] - days[i - 1] + 1 > 30)
                --k;

            // 取三种方案的最小值
            f[i] = min(f[i],
                       min(f[j + 1] + costs[1],
                           f[k + 1] + costs[2]));
        }
        return f[1];
    }
};

3. 复杂度

每个指针只单调移动一次
总体时间复杂度降为：

\[ O(n) \]

五、正序 DP 的双指针写法

1. 状态定义（正序）

定义： \[ f[i] = \text{覆盖前 } i \text{ 个出行日的最小费用} \]

\(f[0] = 0\)
答案为 \(f[n]\)

2. 转移逻辑

考虑第 \(i\) 个出行日：

使用 1 天票：

\[ f[i] = f[i-1] + c_1 \]

使用 7 天票：

设 \(j\) 为最早满足

\[ days[i] - days[j] + 1 \le 7 \]

的出行日下标

则该票覆盖区间 \([j,i]\)，之前需要覆盖 \([1,j-1]\)

\[ f[i] = f[j-1] + c_7 \]

使用 30 天票同理

3. 正序双指针优化代码

class Solution {
public:
    static const int maxn = 4e2 + 5;
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        int f[maxn];

        // f[i]：覆盖前 i 个出行日的最小费用
        f[0] = 0;

        // j, k 分别表示 7 天 / 30 天通行证的最早覆盖下标
        int j = 1, k = 1;

        for (int i = 1; i <= n; ++i) {
            // 1 天游玩票
            f[i] = f[i - 1] + costs[0];

            // 更新 7 天游玩票的左边界
            while (j <= n && days[i - 1] - days[j - 1] + 1 > 7)
                ++j;

            // 更新 30 天游玩票的左边界
            while (k <= n && days[i - 1] - days[k - 1] + 1 > 30)
                ++k;

            // 三种方案取最小
            f[i] = min(f[i],
                       min(f[j - 1] + costs[1],
                           f[k - 1] + costs[2]));
        }
        return f[n];
    }
};

考点

思路