动态规划结合单调队列优化解决补给站最小花费问题

1. 项目概述与问题定义

最近在刷算法题和准备面试的时候，遇到了一个挺有意思的经典问题，我把它叫做“补给站最优花费问题”。乍一看，这像是一个模拟题或者简单的贪心，但深入分析后，发现它其实是一个考察动态规划思想，尤其是“状态机DP”和“决策优化”的绝佳案例。很多朋友在初次接触时，容易陷入“看到低价就买”的直觉陷阱，结果写出来的代码要么超时，要么答案不对。我自己在解决这个问题的过程中，也踩了不少坑，最终摸索出了一套清晰、高效且易于理解的C++实现方案。

简单来说，这个问题描述了一个旅行者（或者车辆）沿着一条直线路径前进，路径上分布着若干个补给站。每个补给站有两个关键信息：距离起点的位置，以及在该站购买单位补给（比如汽油、食物）的价格。旅行者有一个容量上限，即最多能携带多少单位的补给。目标是，从起点出发，到达终点，总路程消耗的补给量是固定的。我们需要规划在哪些补给站购买多少补给，才能使得总花费最小。这本质上是一个在“空间”（位置）和“资源”（补给量）两个维度上的最优决策问题。

这个问题之所以值得深究，是因为它融合了贪心算法的局部最优思想和动态规划的全局面最优保证。你不能只看眼前哪个站便宜，因为你的携带容量限制了你的“囤货”能力；你也不能无脑地在最便宜的站买完所有东西，因为你可能根本到不了那个站。它要求我们在行程的每一步，都根据当前剩余的补给、未来的价格信息，做出一个“瞻前顾后”的决策。接下来，我就结合C++实现，把这个问题从问题分析、思路推导、代码实现到调试心得，完整地梳理一遍。

2. 核心思路与算法设计

2.1 问题建模与关键约束

首先，我们需要把问题抽象成计算机能处理的数据模型。假设有n个补给站，编号0到n-1，其中第0个站是起点，第n-1个站是终点。我们用一个数组dist[i]表示第i个站距离起点的距离，用一个数组price[i]表示在第i个站购买单位补给的价格。注意，终点可能也是一个补给站（价格通常视为0或不购买），也可能只是一个位置点。

旅行者有一个最大携带容量C。假设每单位距离消耗1单位补给，那么从站点i到站点i+1的距离d = dist[i+1] - dist[i]，就需要消耗d单位的补给。这里有一个隐含的可行性条件：任意两站之间的距离必须小于等于容量C，否则旅行者无法直接到达，问题无解。我们在预处理时需要检查这一点。

我们的决策变量是什么？是在每个站点i， 当到达时剩余油量fuel_left的情况下，需要购买多少油量buy。目标是总花费最小。这立刻引导我们想到动态规划。

2.2 动态规划状态设计

最直接的状态设计是：dp[i][f]表示到达第i个补给站，并且此时剩余补给量为f时，所花费的最小成本。其中i的范围是[0, n-1]，f的范围是[0, C]。

状态转移方程如何推导？我们从状态dp[i][f]出发，考虑在站点i的决策：购买b单位补给（0 <= b <= C - f，因为购买后总量不能超过容量C）。购买需要花费b * price[i]。购买后，补给量变为f + b。然后我们出发前往下一个站点i+1，消耗need = dist[i+1] - dist[i]的补给。因此，到达站点i+1时的剩余补给量应为f + b - need。这个值必须非负。

由此，我们可以得到状态转移方程：dp[i+1][f+b-need] = min(dp[i+1][f+b-need], dp[i][f] + b * price[i])其中，b需要遍历所有可能的购买量。

初始化：dp[0][0] = 0，表示在起点剩余油量为0，花费为0。其他状态初始化为无穷大（INF）。

答案：最终答案是dp[n-1][0]，即到达终点时剩余油量为0的最小花费。如果终点不是补给站，我们可能需要允许终点有非零剩余油量，但通常问题会规定到达终点即可，剩余油量不计。这里我们按严格消耗完来处理。

这个DP思路是清晰的，但存在一个效率问题：状态数是O(n * C)，对于每个状态，我们需要枚举购买量b，这又是O(C)的复杂度。总时间复杂度为O(n * C^2)。当C很大时（比如10^4），这个算法是不可接受的。我们需要优化。

2.3 贪心优化与单调队列

观察状态转移方程：dp[i+1][new_f] = min(dp[i][f] + b * price[i])，其中new_f = f + b - need，所以b = new_f + need - f。 我们可以把方程改写为：dp[i+1][new_f] = min_{f} (dp[i][f] - f * price[i]) + (new_f + need) * price[i]其中f的取值范围需要满足0 <= f <= C且new_f + need - f >= 0（即b >= 0）且new_f + need - f <= C - f（即b <= C - f），化简后是关于f的一个窗口范围。

对于固定的new_f和i，我们需要在一个滑动窗口内（f的范围）寻找dp[i][f] - f * price[i]的最小值。这正是一个经典的滑动窗口最小值问题，可以使用单调队列（Monotonic Queue）在O(1)均摊时间内解决。

具体来说，当我们计算dp[i+1][*]时，对于每一个new_f，其对应的f窗口是[low, high]，其中low = max(0, new_f + need - C),high = new_f + need。我们需要维护一个关于f递增，且dp[i][f] - f * price[i]也递增（实际上是维护最小值，所以队列是单调递增的）的队列。这样，队首元素就是当前窗口的最小值。

通过这个优化，我们将内层关于b的O(C)循环，优化为了均摊O(1)的单调队列操作。总时间复杂度降至O(n * C)，空间复杂度O(C)（可以滚动数组优化）。这在C达到几千时是可以接受的。

注意：这个优化是本题的核心难点，也是区分“暴力DP”和“优化DP”的关键。理解这个“变形+滑动窗口最小值”的思想，对于解决许多类似带容量限制的序列决策问题非常有帮助。

3. C++代码实现与逐行解析

理论分析完毕，我们来看代码实现。我会先给出完整代码，然后分段详细解释。

#include <iostream> #include <vector> #include <deque> #include <algorithm> #include <climits> using namespace std; const long long INF = LLONG_MAX / 2; // 防止加法溢出 long long minCostToTravel(vector<int>& dist, vector<int>& price, int capacity) { int n = dist.size(); // 检查可行性：任意相邻两站距离不能超过容量 for (int i = 1; i < n; ++i) { if (dist[i] - dist[i-1] > capacity) { return -1; // 无法到达 } } // dp[0] 和 dp[1] 滚动数组，表示到达前一个站点和当前站点的最小花费 // dp[f] 表示到达某个站点时剩余油量为 f 的最小花费 vector<long long> prev_dp(capacity + 1, INF); vector<long long> curr_dp(capacity + 1, INF); // 初始化：在起点0，剩余油量为0，花费为0 prev_dp[0] = 0; for (int i = 0; i < n - 1; ++i) { // i 表示当前所在的站点，我们要计算到达 i+1 站点的状态 int need = dist[i+1] - dist[i]; // 从 i 到 i+1 需要的油量 fill(curr_dp.begin(), curr_dp.end(), INF); // 重置当前dp数组 // 单调队列优化：维护一个 (f, value) 的队列，value = prev_dp[f] - f * price[i] // 队列保持 value 的单调递增（队首最小） deque<pair<int, long long>> mq; // 遍历到达 i+1 站点时的可能剩余油量 new_f for (int new_f = 0; new_f <= capacity; ++new_f) { // 对于给定的 new_f，在上一站 i 时，油量 f 必须满足： // 1. b = new_f + need - f >= 0 -> f <= new_f + need // 2. b <= capacity - f -> f >= new_f + need - capacity int f_high = new_f + need; int f_low = max(0, new_f + need - capacity); // 将新的候选 f (即 f_high) 加入单调队列 if (f_high <= capacity) { long long candidate_val = prev_dp[f_high] - (long long)f_high * price[i]; // 维护队列单调性：从队尾移除所有值大于等于当前候选值的元素 while (!mq.empty() && mq.back().second >= candidate_val) { mq.pop_back(); } mq.push_back({f_high, candidate_val}); } // 移除窗口外的队首元素（f < f_low） while (!mq.empty() && mq.front().first < f_low) { mq.pop_front(); } // 如果队列不为空，队首就是窗口 [f_low, f_high] 内 value 的最小值 if (!mq.empty()) { long long min_val = mq.front().second; // 状态转移：dp[i+1][new_f] = min_val + (new_f + need) * price[i] curr_dp[new_f] = min_val + (long long)(new_f + need) * price[i]; // 防止溢出和无效状态传播 if (curr_dp[new_f] > INF) curr_dp[new_f] = INF; } // 如果队列为空，说明没有合法的 f 能转移到 new_f，curr_dp[new_f] 保持 INF } // 滚动数组：将 curr_dp 设为下一轮的 prev_dp swap(prev_dp, curr_dp); } // 最终，prev_dp 存储的是到达最后一个站点（终点）时的状态 // 题目通常要求到达终点时油量恰好为0（或允许非负，这里取0） long long ans = prev_dp[0]; return ans >= INF ? -1 : ans; } int main() { // 示例输入 vector<int> dist = {0, 100, 300, 450, 600}; // 站点距离起点的位置 vector<int> price = {5, 9, 3, 8, 0}; // 站点油价，终点价格为0 int capacity = 200; // 油箱容量 long long result = minCostToTravel(dist, price, capacity); if (result == -1) { cout << "无法到达终点！" << endl; } else { cout << "最小总花费为: " << result << endl; } return 0; }

3.1 输入与可行性检查

代码开头定义了距离数组dist和价格数组price，以及油箱容量capacity。首先进行可行性检查：遍历所有相邻站点，如果距离差大于容量C，则直接返回-1，表示问题无解。这是一个重要的边界条件处理，避免算法在不可能的情况下运行。

3.2 DP数组与初始化

我们使用滚动数组prev_dp和curr_dp来节省空间，它们的大小都是capacity + 1，索引代表剩余油量。prev_dp[f]表示到达当前循环的站点 i时剩余油量为f的最小花费。初始化时，我们在起点 (i=0)，剩余油量为0，花费为0，所以prev_dp[0] = 0，其他状态为无穷大 (INF)。

这里INF设置为LLONG_MAX/2是为了防止在状态转移做加法时发生溢出。

3.3 主循环与单调队列优化

主循环for (int i = 0; i < n - 1; ++i)遍历每一个“出发站”i，目标是计算到达下一站i+1的所有状态curr_dp[new_f]。

对于每一个目标状态new_f（到达i+1站时的剩余油量），我们需要找到所有能转移到它的上一站状态f。关系是：b = new_f + need - f，其中need是两站间距离。购买量b必须满足0 <= b <= capacity - f。

我们将状态转移方程重写为寻找prev_dp[f] - f * price[i]在某个f窗口内的最小值。这个窗口[f_low, f_high]是随着new_f变化而滑动的。

单调队列mq的操作是核心：

1. 入队：当计算new_f时，对应的f_high成为一个新的候选f。我们计算其价值value = prev_dp[f_high] - f_high * price[i]，并将其加入队列。在加入前，从队尾弹出所有value大于等于当前候选值的元素，以保证队列的单调递增性（队首始终是最小值）。
2. 出队：检查队首元素对应的f是否已经小于当前窗口的下界f_low，如果是，则弹出队首，因为它已经不在当前有效的窗口内了。
3. 取值：经过上述维护，如果队列不空，队首元素的value就是窗口内的最小值。然后我们用公式curr_dp[new_f] = min_val + (new_f + need) * price[i]完成状态转移。

这个循环结束后，curr_dp就存储了到达站点i+1的所有状态的最小花费。然后通过swap(prev_dp, curr_dp)滚动到下一轮。

3.4 结果提取与测试

循环结束后，prev_dp中存储的是到达最后一个站点（终点）时的状态。根据问题定义，我们通常需要剩余油量为0的最小花费，即prev_dp[0]。如果这个值大于等于INF，说明无法以任何方式在满足条件下到达终点，返回-1。

在main函数中，我给出了一个简单的测试用例。你可以修改dist,price,capacity来验证算法的正确性。

4. 算法正确性分析与复杂度

4.1 为什么贪心（直接在最便宜站买）不行？

这是一个常见的思维误区。假设路径上有三个站A(价格5)、B(价格3)、C(价格8)，容量为100，A到B距离40，B到C距离60。如果只在最便宜的B站买，从A出发时，你必须买至少40单位油（价格5）才能到B。到了B，你油箱里可能还有一点剩余，但为了走完剩下的60，你需要在B买油。然而，如果你在A站有先见之明，知道B站便宜，你可能会在A只买刚好到B的油（40单位），然后在B站加满（100单位），总花费是40*5 + 100*3 = 500。但最优解呢？考虑在A站加满（100单位），花费100*5=500，然后直接开到C站，因为A到C总距离100，刚好用完，不需要在B和C买油，总花费也是500。这个简单例子中两者持平。

但如果容量限制更紧，或者价格分布更复杂，贪心就会出错。例如，容量为50，A(5), B(10), C(3)，A到B距离30，B到C距离30。贪心会在最便宜的C站买，但你必须先到C。从A到B需要30油，你必须在A买至少30（花费150）。到B后，剩余油量20，还需要至少10油才能到C，必须在B买10（花费100），总花费250。最优解是在A加满50（花费250），直接开到C（消耗60，但只能带50，所以此路不通？）。让我们重新设计：容量60，A(5), B(10), C(3)，A到B30，B到C30。贪心：A买30到B（150），B买30到C（300），总450。最优：A买60（300），直接到C，总300。可见贪心并非最优。

因此，必须通过动态规划来考虑所有可能性。

4.2 单调队列优化正确性证明

我们优化后的DP，等价于原始的二维DP。单调队列维护了dp[i][f] - f * price[i]在滑动窗口内的最小值。对于每个new_f，我们通过窗口[f_low, f_high]限制了合法的上一状态f。队列的单调性保证了我们能在O(1)时间内取得最小值，而枚举所有b或f需要O(C)时间。因此，优化没有遗漏任何可能的状态转移，是正确的。

4.3 时间复杂度与空间复杂度

• 时间复杂度：外层循环O(n)，内层对new_f的循环O(C)，每个new_f的操作（入队、出队、取值）是均摊O(1)的。因此总时间复杂度为O(n * C)。
• 空间复杂度：使用了两个一维DP数组prev_dp和curr_dp，大小均为O(C)，以及一个最大容量为O(C)的单调队列。因此总空间复杂度为O(C)。

对于n和C都在几千级别的题目，这个算法是高效的。

5. 常见问题与调试技巧

在实际编写和调试这类DP问题时，很容易遇到一些坑。下面是我总结的几个常见问题和解决技巧。

5.1 整数溢出问题

这是最容易忽略的问题。花费可能是非常大的整数（距离、价格、容量都大）。dp数组和中间计算必须使用long long（64位整数）。INF的设置也要小心，不能直接用LLONG_MAX，因为状态转移中会做加法min_val + (new_f + need) * price[i]，可能导致上溢。通常设置为LLONG_MAX / 2是一个安全的选择。

const long long INF = LLONG_MAX / 2; ... if (curr_dp[new_f] > INF) curr_dp[new_f] = INF; // 额外的保护

5.2 单调队列的实现细节

单调队列的实现需要特别注意：

1. 存储什么：队列里我存储了pair<int, long long>，即f和对应的value。存储f是为了方便判断队首元素是否在窗口内（f < f_low）。
2. 何时入队：对于当前new_f，对应的f_high是新的候选。注意判断f_high <= capacity才入队，因为f不能超过容量。
3. 维护单调性：我们是维护一个值单调递增的队列。所以当新的候选值candidate_val小于等于队尾的值时，要弹出队尾，直到队列为空或队尾值小于候选值，再入队。这样保证了队首始终是窗口内的最小值。
4. 何时出队队首：当队首元素对应的f小于当前窗口下界f_low时，它已经无效，需要弹出。

5.3 边界条件与初始化

• 起点状态：务必正确初始化prev_dp[0] = 0，其他为INF。
• 终点处理：代码中假设终点是最后一个dist，且要求最终剩余油量为0。有些问题可能允许终点剩余油量任意非负值，那么答案就是min(prev_dp[0], prev_dp[1], ..., prev_dp[capacity])。需要仔细阅读题目要求。
• 不可达判断：除了开始的距离检查，DP结束后如果ans仍然是INF，也表示不可达。

5.4 调试与测试用例设计

自己设计几个小规模的测试用例，手动计算预期结果，是调试的最佳方式。

1. 简单案例：两个站，容量足够大。验证是否在起点买了刚好够的油。
2. 容量限制案例：三个站，容量较小，迫使必须在中间站加油。验证决策是否正确。
3. 价格波动案例：价格高低交错，验证算法是否会在低价站“囤货”。
4. 不可达案例：两站距离超过容量，验证是否返回-1。

例如：

// 测试1：简单两站 dist = {0, 100}, price = {5, 0}, capacity=200。 预期：在起点买100油，花费500。算法应返回500。 // 测试2：容量限制 dist = {0, 50, 100}, price = {10, 1, 0}, capacity=60。 分析：从0到50需50油。最优策略：在0站买50油（花费500）到1站，在1站加满到60油（花费60），然后到2站消耗50油，剩10油（但终点油量要求为0，可能需要调整）。如果要求终点油量为0，则在1站只需买50油（花费50），总花费550。

可以使用打印DP数组的方式来跟踪状态转移过程，对于小容量（比如C=5）的情况非常直观。

5.5 算法变种与扩展

这个“补给站问题”有很多变种：

• 初始油量非零：旅行者起点有一定油量init_fuel。只需修改初始化：prev_dp[init_fuel] = 0。
• 油量消耗非1:1：可能每单位距离消耗k单位油。只需将need的计算改为k * (dist[i+1] - dist[i])，并相应调整容量和状态表示。
• 多个资源维度：例如同时考虑油量和食物，变成二维DP，复杂度会大大增加。
• 目标函数变化：不是求最小花费，而是求在给定预算下的最远距离，或者求最小最大单次购买量等。

理解了这个核心模型和单调队列优化技巧，你就能应对大多数线性序列上的带容量资源调度问题了。这不仅仅是道算法题，其思想在物流路径规划、资源采购策略等实际场景中也有应用。下次遇到类似问题，不妨先想想能不能套用这个“状态表示 + 滑动窗口优化”的框架。