飞机加什么油源码深度剖析：搞定这道高频面试题

别再说你只会背八股文了。很多开发者盯着【飞机加什么油】这道题，语法滚瓜烂熟，代码敲得飞起，但一到项目实战或者面试深挖，脑子就一片空白。这就是典型的“学会语法却不知怎么搭项目”。

这道题之所以常年霸榜【高频面试题】，不是因为它难，而是因为它能像照妖镜一样，照出你对动态规划（DP）底层逻辑的理解深度。面试官问的从来不是“你会不会写”，而是“你懂不懂为什么这么写”，以及“如果状态空间爆炸了，你怎么办”。

今天，咱们不玩虚的，直接拆解这道题的底层骨架。我会把抽象的算法逻辑，拆解成你能直接用在生产环境里的思维模型。不管你是准备跳槽，还是想在架构设计上更进一步，这篇文章都能帮你把这块硬骨头啃下来。

一句话原理：用空间换时间的状态机

先抛开那些复杂的数学公式，【飞机加什么油】的核心本质是什么？

它是一个典型的“无后效性”问题，利用动态规划（DP）构建状态机，将指数级的暴力搜索压缩为多项式时间的求解过程。

想象一下，你在玩一个升级游戏。每到一个加油站，你都要做一个决定：加多少油？加多了，油箱可能溢出（如果限制了最大容量），或者浪费金钱；加少了，可能到不了下一个站。

暴力解法是怎么做的？枚举每一个站点的加油量。如果加油站有 N 个，每个站能加 1 到 100 升油，复杂度直接爆炸。

DP 解法是怎么做的？我们定义一个状态：dp[i][j] 表示“到达第 i 个加油站时，油箱里恰好有 j 升油”的最小花费（或最大剩余油量，视题目变种而定）。

核心逻辑只有一句话： 当前状态 dp[i][j] 的最优解，一定依赖于前一个状态 dp[i-1][k] 加上从 i-1 到 i 消耗的油量，以及在本站加油的动作。

这就是“无后效性”：一旦你确定了到达第 i 个站时的油量 j，你之前是怎么加的油、经过哪些路，已经不再重要了，未来的决策只取决于当前的油量 j。

类比解释：地铁换乘与预算控制

为了让你彻底理解这个状态转移，我们用一个更生活化的类比：地铁通勤预算。

假设你要从家（起点）到公司（终点），中间经过 5 个换乘站。

油箱里的油 = 你口袋里的余额。
加油站 = 地铁站。
加油 = 充值。
耗油 = 坐地铁花钱。

场景痛点： 你不想多花钱（最小化成本），也不想余额太多闲置（如果题目要求最大化剩余，则是另一回事，这里以最小化成本为例，这是【飞机加什么油】最常见的变种）。

错误思维（贪心陷阱）： 很多人直觉认为：“哪里油价便宜就在哪里加满”。错！如果下一站油价更便宜，且你油箱够大，你应该只加刚好够到下一站的油，而不是加满。但如果下一站很贵，而当前站便宜，且再下一站更贵，那你可能需要在当前站多加一点，覆盖到那个更贵的站。

正确思维（DP 状态机）： 我们不看全局，只看“局部最优组合出全局最优”。定义状态：Cost[i][j] = 到达第 i 站，余额为 j 时的最小累计花费。

状态转移方程（通俗版）： Cost[i][j] = Min( 所有可能的 Cost[i-1][k] + Cost_to_fill(j - k - fuel_consumed) ) 其中 k 是上一站的余额，j 是本站的目标余额，fuel_consumed 是路上耗的油。

这个公式的意思是：要得到“我在第 i 站有 j 元”这个状态，我可能是从“第 i-1 站有 k 元”的状态过来的。我在路上花了 fuel_consumed，所以我到了第 i-1 站时，实际可用余额是 j - fuel_consumed。等等，逻辑反了。应该是：我在第 i-1 站有 k 元，路上花了 c 元，到达第 i 站时剩 k - c 元。为了凑够当前的 j 元，我需要在第 i 站充值 j - (k - c) 元。所以总花费 = Cost[i-1][k] + (j - (k - c)) * price[i]。

这就是底层原理：枚举前驱状态，计算转移代价，取最小值。

源码/伪代码片段：从逻辑到代码的落地

光说不练假把式。下面是一段 Python 实现，展示了如何构建这个 DP 表。请注意代码中的注释，每一行都对应着前面的原理。

def min_cost_to_fly(stations, distances, tank_capacity):"""计算飞机加什么油的最小成本:param stations: 油价列表，stations[i] 表示第 i 站的油价:param distances: 距离列表，distances[i] 表示从第 i 站到第 i+1 站的耗油量:param tank_capacity: 油箱最大容量:return: 最小成本"""n = len(stations)# 初始化 DP 表，inf 表示不可达# dp[i][j] 表示到达第 i 站，油箱剩余 j 升油的最小成本# 注意：j 的范围是 0 到 tank_capacitydp = [[float('inf')] * (tank_capacity + 1) for _ in range(n)]# 初始状态：在第 0 站，油箱为空，成本为 0# 或者我们可以假设出发前必须加满，这里假设从空油箱开始，需在0站加油dp[0][0] = 0.0for i in range(n - 1):for current_fuel in range(tank_capacity + 1):# 如果当前状态不可达，跳过if dp[i][current_fuel] == float('inf'):continue# 计算从第 i 站到第 i+1 站的耗油量cost_to_next = distances[i]# 检查油量是否足够到达下一站if current_fuel < cost_to_next:continue# 到达下一站时的剩余油量next_fuel_remaining = current_fuel - cost_to_next# 枚举在下一站加油后的油量 next_fuel# next_fuel 可以是 next_fuel_remaining 到 tank_capacity 之间的任意值for next_fuel in range(next_fuel_remaining, tank_capacity + 1):# 需要加的油量fuel_to_add = next_fuel - next_fuel_remaining# 加油成本 = 加油量 * 下一站油价refill_cost = fuel_to_add * stations[i + 1]# 总成本 = 上一站成本 + 本次加油成本total_cost = dp[i][current_fuel] + refill_cost# 状态转移：取最小值if total_cost < dp[i + 1][next_fuel]:dp[i + 1][next_fuel] = total_cost# 答案在第 n-1 站，任何油量下的最小值# 通常题目要求到达终点即可，不要求特定剩余油量min_final_cost = min(dp[n - 1])# 如果 min_final_cost 还是 inf，说明无法到达return min_final_cost if min_final_cost != float('inf') else -1# 示例数据
# 5个站，油价分别为 [1, 2, 1, 3, 1]
# 距离分别为 [3, 2, 4, 1] (耗油量)
# 油箱容量 5
stations = [1, 2, 1, 3, 1]
distances = [3, 2, 4, 1]
capacity = 5print(f"最小成本: {min_cost_to_fly(stations, distances, capacity)}")

逐行解析关键点：

dp 数组的维度：为什么是二维？因为“到达哪一站”和“剩多少油”共同构成了唯一的状态。如果是一维 DP，我们就丢失了“油量”这个关键信息，无法判断是否还能到达下一站。
current_fuel < cost_to_next 的剪枝：这是物理约束。如果油不够，这个状态直接废弃。这能大幅减少无效计算，也是面试中体现“工程思维”的地方——永远先检查边界和非法状态。
内层循环 next_fuel：这是状态转移的核心。我们在枚举“在下一站加完油后，油箱里到底有多少油”。这个枚举范围是从“刚好够到”到“加满”。为什么？因为加得越多，后续选择越多，但当前成本也越高。DP 会帮我们权衡这个“现在多花点”和“以后可能少花点”的关系。

流程描述：从暴力到 DP 的思维跃迁

为了让你更直观地看到 DP 是如何“填表”的，我们用一个极简案例走一遍流程。

案例：

站 A (价 1), 站 B (价 10), 站 C (价 1)
A->B 耗 2 升, B->C 耗 2 升
油箱容量 4 升

Step 1: 初始化 在站 A，油量为 0，成本 0。 dp[0][0] = 0

Step 2: 从 A 到 B 在 A 站，我们需要决定加多少油才能到 B。 A 到 B 需要 2 升。

如果在 A 加 2 升：
- 到达 B 时剩 0 升。
- 成本 = 0 (初始) + 2 * 1 (A站价) = 2。
- 更新 dp[1][0] = 2。
如果在 A 加 3 升：
- 到达 B 时剩 1 升。
- 成本 = 0 + 3 * 1 = 3。
- 更新 dp[1][1] = 3。
如果在 A 加 4 升（加满）：
- 到达 B 时剩 2 升。
- 成本 = 0 + 4 * 1 = 4。
- 更新 dp[1][2] = 4。
如果在 A 加 5 升？不行，容量限制 4。

此时，B 站的状态表 dp[1] 为： [2, 3, 4, inf, inf] 索引 0: 剩0升, 成本2 索引 1: 剩1升, 成本3 索引 2: 剩2升, 成本4

Step 3: 从 B 到 C B 到 C 需要 2 升。我们需要遍历 B 站的所有有效状态。

从 B 站状态 [剩0升, 成本2] 出发：
- 油不够 (0 < 2)，无法到达 C。剪枝。
从 B 站状态 [剩1升, 成本3] 出发：
- 油不够 (1 < 2)，无法到达 C。剪枝。
从 B 站状态 [剩2升, 成本4] 出发：
- 油刚好够 (2 >= 2)。
- 到达 C 时剩 0 升。
- 需要在 C 站加油吗？题目通常只要求到达终点，如果 C 是终点，不需要再加油。
- 如果 C 不是终点，假设后面还有路，我们需要枚举在 C 加油后的状态。
- 这里假设 C 是终点，我们只关心到达 C 的成本。
- 成本保持 4。
- 更新 dp[2][0] = 4。

结论： 最小成本是 4。 策略复盘： 在 A 站加满 4 升（成本 4），开到 B 剩 2 升，再开到 C 剩 0 升。 对比贪心： 如果在 A 只加 2 升（成本 2），到 B 剩 0。在 B 必须加 2 升（成本 2 + 2*10 = 22）。总成本 22。 DP 的优势： 它自动发现了“在便宜的 A 站多存一点油，避开昂贵的 B 站”这一策略，而不需要人为预设规则。

实战验证：生产环境中的坑与优化

在实际项目中，或者更复杂的变体中（比如【飞机加什么油】的变种：加油站有营业时间、油价随时间波动、飞机有最大载重限制等），上述基础 DP 可能会遇到性能瓶颈。

1. 空间优化：滚动数组 观察状态转移方程，dp[i] 只依赖 dp[i-1]。我们可以把二维数组 dp[n][capacity+1] 优化为一维数组 dp[capacity+1]，只保留当前行和上一行。

# 空间优化版伪代码
prev_dp = [inf] * (capacity + 1)
prev_dp[0] = 0for i in range(n - 1):curr_dp = [inf] * (capacity + 1)for current_fuel in range(capacity + 1):if prev_dp[current_fuel] == inf: continueif current_fuel < distances[i]: continuenext_remaining = current_fuel - distances[i]for next_fuel in range(next_remaining, capacity + 1):cost = prev_dp[current_fuel] + (next_fuel - next_remaining) * stations[i+1]if cost < curr_dp[next_fuel]:curr_dp[next_fuel] = costprev_dp = curr_dp

这将空间复杂度从 O(N*C) 降到了 O(C)，对于油箱容量极大的场景至关重要。

2. 时间优化：单调队列或凸优化 如果油价满足某些单调性（比如先降后升），状态转移中的 Min 操作可以用单调队列优化，将复杂度从 O(NC^2) 降到 O(NC)。这在处理【高频面试题】的 Hard 变种时经常考到。你需要理解：DP 的内层循环本质上是在求一个线性函数的最小值，如果斜率单调，就可以用数据结构加速。

3. 数据校验与异常处理 在生产代码中，一定要检查：

distances[i] 是否超过 tank_capacity？如果某一段路程耗油超过油箱容量，直接返回 -1（不可达）。
油价是否为负数？逻辑上不合理，需做输入校验。
浮点数精度问题：如果油价是小数，累加多次后可能有精度误差。在涉及金额的计算中，建议使用 Decimal 或整数（乘以 100 转为分）来避免精度丢失。参考 Python 标准库的 decimal 模块文档，或者在 Java 中使用 BigDecimal。

4. 调试技巧 在调试 DP 问题时，打印中间状态表是最有效的手段。不要只看最终结果，要打印 dp[i] 每一行的值，人工验证前几行是否符合逻辑。例如，检查 dp[1] 是否正确反映了在 A 站加油的所有可能成本。如果第一行就错了，后面全错。

总结： 【飞机加什么油】不仅是一道算法题，更是动态规划思维的缩影。