LeetCode 787. K 站中转内最便宜的航班

字数 2673 2025-12-07 15:18:12

LeetCode 787. K 站中转内最便宜的航班

题目描述
有 n 个城市通过一定数量的航班连接。给定一个数组 flights，其中 flights[i] = [fromᵢ, toᵢ, priceᵢ] 表示从城市 fromᵢ 到城市 toᵢ 的航班价格为 priceᵢ。
同时给你三个整数 src、dst 和 k，分别表示出发城市、目标城市和中转次数上限。
你需要找出从 src 到 dst 最多经过 k 次中转（也就是最多乘坐 k+1 趟航班）的最便宜价格。如果不存在这样的路线，则返回 -1。

示例：
输入：n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
输出：200
解释：从城市 0 到城市 2 在 1 次中转内（即最多两趟航班），最便宜的路线是 0 → 1 → 2，总价格 100 + 100 = 200。

解题过程

这个问题本质上是带约束的最短路径问题，约束条件是路径的边数（航班次数）不能超过 k+1。我们可以用动态规划或Bellman-Ford算法的变种来解决，这里我们用动态规划的思路来循序渐进地讲解。

第一步：理解状态定义
动态规划的核心是定义状态。在这个问题中，我们需要记录从起点出发，经过一定次数的航班，到达某个城市的最小花费。
因此，我们可以定义：
dp[t][v] 表示从 src 出发，经过最多 t 次航班（即最多 t-1 次中转），到达城市 v 的最小花费。
注意：这里 t 表示的是航班次数，而不是中转次数。题目允许最多 k 次中转，即最多 k+1 次航班。
所以，t 的范围是 0 到 k+1。

第二步：初始状态

如果出发点就是 src，且不需要坐飞机（航班次数为 0），那么花费是 0。
即：dp[0][src] = 0。
对于其他所有城市，在航班次数为 0 时，从 src 到达它们是不可能的，所以花费设为无穷大（INF）。
即：dp[0][v] = INF（v ≠ src）。

第三步：状态转移方程
我们考虑如何从 t-1 次航班的情况推出 t 次航班的情况。
对于第 t 次航班（即当前航班次数上限为 t），我们到达城市 v 的最小花费有两种可能：

之前就已经在 t-1 次航班内到达了 v，即 dp[t-1][v]。
我们通过一次飞行，从某个城市 u 飞到 v，而到达 u 是在 t-1 次航班内完成的，所以总花费是 dp[t-1][u] + price(u, v)。

因此，状态转移方程为：
dp[t][v] = min( dp[t-1][v], dp[t-1][u] + price(u, v) )，其中存在航班 u -> v 且价格为 price(u, v)。

第四步：遍历顺序

外层循环：航班次数 t 从 1 到 k+1（因为 0 次航班已经初始化过了）。
内层循环：遍历所有航班 [u, v, price]，尝试用航班 u -> v 来更新 dp[t][v]。

这样做可以保证每次更新时，dp[t-1][u] 已经是确定的（因为外层 t 从小到大）。

第五步：答案获取
最终答案应该是 dp[k+1][dst]，即最多 k+1 次航班到达 dst 的最小花费。
如果这个值仍然是无穷大，说明无法在限制内到达，返回 -1。

第六步：空间优化
注意到 dp[t][v] 只依赖于 dp[t-1][...]，所以我们可以用两个一维数组滚动更新，节省空间。

用 prev 数组表示 dp[t-1]。
用 curr 数组表示 dp[t]。
每完成一次 t 的循环，就把 curr 复制给 prev，进行下一轮。

第七步：举例推演
以题目示例为例：n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1。
初始化：prev = [0, INF, INF]（表示 0 次航班时，只有 src=0 的花费是 0）。
k=1 表示最多 1 次中转，即最多 2 次航班，所以 t 从 1 到 2。

t=1（最多 1 次航班）：
- 初始 curr = prev 的副本 [0, INF, INF]。
- 遍历航班：
  - 0→1 价格 100：curr[1] = min(INF, prev[0]+100) = 100。
  - 1→2 价格 100：curr[2] = min(INF, prev[1]+100) = INF（因为 prev[1] 是 INF）。
  - 0→2 价格 500：curr[2] = min(INF, prev[0]+500) = 500。
- 更新后 curr = [0, 100, 500]，复制给 prev。
t=2（最多 2 次航班）：
- 初始 curr = prev 的副本 [0, 100, 500]。
- 遍历航班：
  - 0→1 价格 100：curr[1] = min(100, prev[0]+100) = 100。
  - 1→2 价格 100：curr[2] = min(500, prev[1]+100) = min(500, 200) = 200。
  - 0→2 价格 500：curr[2] = min(200, prev[0]+500) = 200。
- 最终 curr[2] = 200。

答案：curr[dst] = 200。

第八步：边界情况

如果 src == dst 且 k >= 0，花费为 0（不用坐飞机）。
如果没有航班能从 src 出发，则直接返回 -1。
注意 INF 要取一个足够大的值，比如 10^9，避免加法溢出。

总结
这个问题通过动态规划，将“最多 k 次中转”转化为“最多 k+1 次航班”，用航班次数作为阶段，逐步更新到达每个城市的最小花费。最终在 t = k+1 时取 dst 的值即可。这种方法的时间复杂度是 O((k+1) * E)，其中 E 是航班数量，空间复杂度 O(n)。

LeetCode 787. K 站中转内最便宜的航班题目描述有 n 个城市通过一定数量的航班连接。给定一个数组 flights ，其中 flights[i] = [fromᵢ, toᵢ, priceᵢ] 表示从城市 fromᵢ 到城市 toᵢ 的航班价格为 priceᵢ 。同时给你三个整数 src 、 dst 和 k ，分别表示出发城市、目标城市和中转次数上限。你需要找出从 src 到 dst 最多经过 k 次中转（也就是最多乘坐 k+1 趟航班）的最便宜价格。如果不存在这样的路线，则返回 -1 。示例：输入： n = 3 , flights = [[0,1,100],[1,2,100],[0,2,500]] , src = 0 , dst = 2 , k = 1 输出： 200 解释：从城市 0 到城市 2 在 1 次中转内（即最多两趟航班），最便宜的路线是 0 → 1 → 2 ，总价格 100 + 100 = 200。解题过程这个问题本质上是带约束的最短路径问题，约束条件是路径的边数（航班次数）不能超过 k+1 。我们可以用动态规划或 Bellman-Ford算法的变种来解决，这里我们用动态规划的思路来循序渐进地讲解。第一步：理解状态定义动态规划的核心是定义状态。在这个问题中，我们需要记录从起点出发，经过一定次数的航班，到达某个城市的最小花费。因此，我们可以定义： dp[t][v] 表示从 src 出发，经过最多 t 次航班（即最多 t-1 次中转），到达城市 v 的最小花费。注意：这里 t 表示的是航班次数，而不是中转次数。题目允许最多 k 次中转，即最多 k+1 次航班。所以， t 的范围是 0 到 k+1 。第二步：初始状态如果出发点就是 src ，且不需要坐飞机（航班次数为 0），那么花费是 0。即： dp[0][src] = 0 。对于其他所有城市，在航班次数为 0 时，从 src 到达它们是不可能的，所以花费设为无穷大（ INF ）。即： dp[0][v] = INF （v ≠ src）。第三步：状态转移方程我们考虑如何从 t-1 次航班的情况推出 t 次航班的情况。对于第 t 次航班（即当前航班次数上限为 t ），我们到达城市 v 的最小花费有两种可能：之前就已经在 t-1 次航班内到达了 v ，即 dp[t-1][v] 。我们通过一次飞行，从某个城市 u 飞到 v ，而到达 u 是在 t-1 次航班内完成的，所以总花费是 dp[t-1][u] + price(u, v) 。因此，状态转移方程为： dp[t][v] = min( dp[t-1][v], dp[t-1][u] + price(u, v) ) ，其中存在航班 u -> v 且价格为 price(u, v) 。第四步：遍历顺序外层循环：航班次数 t 从 1 到 k+1 （因为 0 次航班已经初始化过了）。内层循环：遍历所有航班 [u, v, price] ，尝试用航班 u -> v 来更新 dp[t][v] 。这样做可以保证每次更新时， dp[t-1][u] 已经是确定的（因为外层 t 从小到大）。第五步：答案获取最终答案应该是 dp[k+1][dst] ，即最多 k+1 次航班到达 dst 的最小花费。如果这个值仍然是无穷大，说明无法在限制内到达，返回 -1 。第六步：空间优化注意到 dp[t][v] 只依赖于 dp[t-1][...] ，所以我们可以用两个一维数组滚动更新，节省空间。用 prev 数组表示 dp[t-1] 。用 curr 数组表示 dp[t] 。每完成一次 t 的循环，就把 curr 复制给 prev ，进行下一轮。第七步：举例推演以题目示例为例： n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1 。初始化： prev = [0, INF, INF] （表示 0 次航班时，只有 src=0 的花费是 0）。 k=1 表示最多 1 次中转，即最多 2 次航班，所以 t 从 1 到 2。 t=1（最多 1 次航班）：初始 curr = prev 的副本 [0, INF, INF] 。遍历航班： 0→1 价格 100： curr[1] = min(INF, prev[0]+100) = 100 。 1→2 价格 100： curr[2] = min(INF, prev[1]+100) = INF （因为 prev[ 1 ] 是 INF）。 0→2 价格 500： curr[2] = min(INF, prev[0]+500) = 500 。更新后 curr = [0, 100, 500] ，复制给 prev 。 t=2（最多 2 次航班）：初始 curr = prev 的副本 [0, 100, 500] 。遍历航班： 0→1 价格 100： curr[1] = min(100, prev[0]+100) = 100 。 1→2 价格 100： curr[2] = min(500, prev[1]+100) = min(500, 200) = 200 。 0→2 价格 500： curr[2] = min(200, prev[0]+500) = 200 。最终 curr[2] = 200 。答案： curr[dst] = 200 。第八步：边界情况如果 src == dst 且 k >= 0 ，花费为 0（不用坐飞机）。如果没有航班能从 src 出发，则直接返回 -1。注意 INF 要取一个足够大的值，比如 10^9 ，避免加法溢出。总结这个问题通过动态规划，将“最多 k 次中转”转化为“最多 k+1 次航班”，用航班次数作为阶段，逐步更新到达每个城市的最小花费。最终在 t = k+1 时取 dst 的值即可。这种方法的时间复杂度是 O((k+1) * E)，其中 E 是航班数量，空间复杂度 O(n)。