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

题目描述
有 n 个城市通过一些航班连接。给定一个数组 flights，其中 flights[i] = [fromᵢ, toᵢ, priceᵢ] 表示从城市 fromᵢ 到城市 toᵢ 的航班价格为 priceᵢ。
现在给定三个整数：n、src（出发城市）、dst（目标城市）和 k（最多经过的中转站数量，即最多可以乘坐 k+1 趟航班）。
请找出从 src 到 dst 最多经过 k 次中转（即最多乘坐 k+1 趟航班）的最便宜价格。如果不存在这样的路线，返回 -1。

解题过程循序渐进讲解

第一步：理解问题与约束条件

• 这是带限制的最短路径问题，限制条件是最多乘坐 k+1 趟航班。
• 可以把每个航班看作一条有向边，权重是价格。
• 由于价格都是非负的，但有限制条件，不能直接用 Dijkstra（因为 Dijkstra 是按距离贪心，无法直接处理“步数限制”）。
• 一种思路是动态规划（DP），把“步数”作为一个维度。

第二步：定义动态规划状态
定义：
dp[t][i] = 从 src 出发，恰好经过 t 次航班（即中转 t-1 次），到达城市 i 的最小价格。
注意：t 表示已乘坐的航班数量，取值范围是 0 到 k+1（因为最多 k+1 趟航班）。
初始状态：

• dp[0][src] = 0（在起点，还没坐飞机，价格为 0）
• 对于其他城市 i ≠ src，dp[0][i] = ∞（不可能 0 趟航班到达）

第三步：状态转移方程
对于航班 (u, v, price)：
如果我们在第 t-1 趟航班时到达了 u（花费 dp[t-1][u]），那么可以乘坐这趟航班到 v，总花费 = dp[t-1][u] + price。
所以转移方程为：
dp[t][v] = min(dp[t][v], dp[t-1][u] + price)
对所有航班遍历，更新 dp 表。

第四步：DP 实现细节

• 初始化一个二维数组 dp[k+2][n]，所有值设为无穷大（表示不可达）。
• dp[0][src] = 0。
• 外层循环 t 从 1 到 k+1（表示增加一趟航班）：
  • 内层遍历所有航班 (u, v, price)：
    • 如果 dp[t-1][u] 不是无穷大，说明可以从 u 出发：
      • dp[t][v] = min(dp[t][v], dp[t-1][u] + price)
• 最终答案：在 dp[1][dst] 到 dp[k+1][dst] 中取最小值（因为允许 1 到 k+1 趟航班到达目标）。
• 如果没有可达值，返回 -1。

第五步：空间优化
注意到 dp[t] 只依赖于 dp[t-1]，可以压缩为两个一维数组：prev 和 curr，交替更新。

• 初始化 prev 数组，prev[src] = 0，其他为无穷大。
• 对 t 从 1 到 k+1：
  • curr 数组初始化为无穷大。
  • 遍历航班 (u, v, price)：
    • 如果 prev[u] 不是无穷大，则 curr[v] = min(curr[v], prev[u] + price)。
  • 将 curr 赋值给 prev，继续下一轮。
• 最终答案在 prev[dst] 中（注意：这里最后 prev 对应的是最后一趟航班的结果，但我们要取的是所有 t ≤ k+1 的最小值，所以需要在每次更新后记录最小值，或最后再检查所有 prev 状态）。

更保险：用一个变量 ans 在每轮更新后，如果到达 dst 就记录最小值。

第六步：举例验证
例：n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
最多 k+1=2 趟航班。
初始：prev=[0, ∞, ∞]
t=1（第一趟航班）：

• 航班(0,1,100)：curr[1]=100
• 航班(0,2,500)：curr[2]=500
  此时 ans = 500（从 0 直飞 2）
  t=2（第二趟航班）：
  此时 prev=[0,100,500]（这里注意 prev 是上一轮结果，但为了空间优化，我们实际应该用上一轮的 curr 作为这一轮的 prev，这里举例时按步骤来）
  更正确步骤：
  t=1 后 prev=[0,100,500]
  t=2：curr 初始无穷大，遍历航班：
  (0,1,100)：prev[0]=0 ⇒ curr[1]=100（但更小值100已存在，不影响）
  (1,2,100)：prev[1]=100 ⇒ curr[2]=200
  (0,2,500)：prev[0]=0 ⇒ curr[2]=min(200,500)=200
  此时 ans = min(500,200) = 200，符合预期（0→1→2 两趟航班 200 元，比直飞 500 元便宜）。

第七步：复杂度分析

• 时间复杂度：O(k × E)，其中 E 是航班数量。
• 空间复杂度：O(n)（优化后）。

第八步：边界情况

• 如果 src == dst，价格应该是 0（不需要航班）。
• 如果 k=0，只能直飞，检查是否有航班 src→dst。
• 如果无可行路线，返回 -1。

最终答案实现（Python 风格伪代码）

def findCheapestPrice(n, flights, src, dst, k):
    INF = 10**9
    prev = [INF] * n
    prev[src] = 0
    ans = INF
    for t in range(1, k+2):  # 最多 k+1 趟航班
        curr = [INF] * n
        for u, v, price in flights:
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + price)
        ans = min(ans, curr[dst])
        prev = curr
    return ans if ans != INF else -1