871. 最低加油次数

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • 线性DP
  • 贪心
  • 优先队列

思路

1. 问题描述

给定：

  • 目标位置：\(\text{target}\)
  • 起始油量：\(\text{startFuel}\)
  • \(n\) 个加油站，按位置升序给出 第 \(i\) 个站点位于 \(\text{pos}_i\)，可提供 \(\text{fuel}_i\) 的油量

车辆从位置 \(0\) 出发，油量为 \(\text{startFuel}\)，每前进 \(1\) 单位距离消耗 \(1\) 单位油。

目标：以 最少的加油次数 到达位置 \(\text{target}\)；若无法到达，返回 \(-1\)。

2. 设计视角总览

该问题的关键困难在于：

“最少加油次数”并不是一个容易直接递推的量， 因为是否还能继续前进，取决于当前最远可达距离。

因此，主流解法都会把问题重构为：

在固定加油次数的条件下，最多能到达多远？

围绕这一思想，有三种等价但实现方式不同的解法：

  1. 二维动态规划（最直观、最易证明）
  2. 一维动态规划（二维 DP 的空间压缩）
  3. 贪心 + 最大堆（对 DP 的“在线化 / 最短路化”优化）

3. 二维动态规划（核心讲解）

3.1 状态定义

设加油站已按位置升序排列，编号为 \(1 \sim n\)。

定义状态： \[ f[i][j] = \begin{cases} \text{在只考虑前 } i \text{ 个加油站的前提下} \\ \text{恰好加油 } j \text{ 次所能到达的最远距离} \end{cases} \] 该状态的含义非常重要：

  • \(i\) 控制“可用的站点集合”
  • \(j\) 精确计数加油次数
  • \(f[i][j]\) 将所有路径与剩余油量信息压缩为一个“最远可达边界”

3.2 初始化

  • 不使用任何加油站、且不加油：

\[ f[0][0] = \text{startFuel} \]

  • 其余状态均不可达（初始化为 \(0\) 或负无穷）

3.3 状态转移

考虑第 \(i\) 个加油站（位置 \(\text{pos}_i\)，油量 \(\text{fuel}_i\)）。

对每个 \(j = 0 \sim i\)，有两种选择：

情况一：不在第 \(i\) 个站加油

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

情况二：在第 \(i\) 个站加油一次

前提是：必须能到达该站点 \[ f[i-1][j-1] \ge \text{pos}_i \] 若满足，则： \[ f[i][j] = \max\left( f[i][j],\; f[i-1][j-1] + \text{fuel}_i \right) \]

3.4 答案提取

当所有站点处理完毕后，在最后一行中寻找最小的 \(j\) 使得： \[ f[n][j] \ge \text{target} \] 该 \(j\) 即为最少加油次数；若不存在，则返回 \(-1\)。

4. 一维动态规划（空间压缩）

4.1 压缩思想

由于状态转移只依赖于上一行 \(f[i-1][\cdot]\)， 可以将二维数组压缩为一维数组： \[ f[j] = \text{当前阶段下，加油 } j \text{ 次的最远可达距离} \]

4.2 关键实现要点

  • 必须从大到小枚举 \(j\)
  • 防止同一加油站在同一轮中被使用多次（0/1 背包经典要求）

5. 贪心 + 最大堆

5.1 核心思想

将问题理解为：

在向前推进的过程中， 当“当前可达距离不足以到达下一个站点”时， 必须增加一次加油操作。

而既然必须加油：

应当优先选择此前经过的站点中，油量最大的那一次加油。

这是一种“延迟决策”的贪心策略。

5.2 算法流程

  1. 将终点 \(\text{target}\) 视作一个油量为 \(0\) 的虚拟站点
  2. 维护：
    • 当前最远可达距离 fuel
    • 一个最大堆，保存“已经经过但尚未使用的站点油量”
  3. 顺序扫描站点：
    • 若 fuel < pos，则从堆中取最大油量补充（加油次数 +1）
    • 若堆空仍无法到达，则返回 \(-1\)
    • 将当前站点的油量加入堆

6. 参考实现（带注释）

6.1 二维 DP（AC）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int minRefuelStops(int target, int startFuel,
                       vector<vector<int>>& stations) {
        // f[i][j]: 只考虑前 i 个站点，加油 j 次，能到达的最远距离
        unsigned f[505][505];
        int n = stations.size();

        // 初始化：不加油时，最远只能到 startFuel
        for (int i = 0; i <= n; ++i)
            f[i][0] = startFuel;

        // 状态转移
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                f[i][j] = 0;

                // 不在第 i 个站加油
                if (f[i - 1][j] >= stations[i - 1][0])
                    f[i][j] = f[i - 1][j];

                // 在第 i 个站加油一次
                if (f[i - 1][j - 1] >= stations[i - 1][0])
                    f[i][j] = max(
                        f[i][j],
                        f[i - 1][j - 1] + stations[i - 1][1]
                    );
            }
        }

        // 寻找最小加油次数
        for (int j = 0; j <= n; ++j) {
            if (f[n][j] >= target)
                return j;
        }
        return -1;
    }
};

6.2 一维 DP（空间压缩）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int minRefuelStops(int target, int startFuel,
                       vector<vector<int>>& stations) {
        // f[j]: 加油 j 次，当前能到达的最远距离
        unsigned f[505];
        int n = stations.size();

        f[0] = startFuel;

        for (int i = 1; i <= n; ++i) {
            // 倒序枚举，防止同一站点被重复使用
            for (int j = i; j >= 1; --j) {
                // 若此前不可达当前站点，则该状态失效
                if (f[j] < stations[i - 1][0])
                    f[j] = 0;

                // 尝试在当前站点加油
                if (f[j - 1] >= stations[i - 1][0])
                    f[j] = max(
                        f[j],
                        f[j - 1] + stations[i - 1][1]
                    );
            }
        }

        for (int j = 0; j <= n; ++j) {
            if (f[j] >= target)
                return j;
        }
        return -1;
    }
};

6.3 贪心 + 最大堆（AC）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int minRefuelStops(int target, int startFuel,
                       vector<vector<int>>& stations) {
        int ans = 0;

        // 将终点视作油量为 0 的虚拟站点
        stations.push_back({target, 0});

        priority_queue<int> q;   // 最大堆：保存可用油量
        int fuel = startFuel;    // 当前最远可达距离

        for (int i = 0; i < stations.size(); ++i) {
            int pos = stations[i][0];
            int gas = stations[i][1];

            // 若当前可达距离不足，必须加油
            while (!q.empty() && fuel < pos) {
                fuel += q.top();
                q.pop();
                ++ans;
            }

            // 堆空仍无法到达
            if (fuel < pos)
                return -1;

            // 当前站点进入“可用加油集合”
            q.push(gas);
        }
        return ans;
    }
};