好的，我为你讲解一个尚未出现在你已记录列表中的线性动态规划经典题目。

线性动态规划：K 站中转内最便宜的航班

题目描述

有 n 个城市，编号从 0 到 n-1。现在给你一个航班列表 flights，其中每个航班 flights[i] = [from_i, to_i, price_i] 表示从城市 from_i 飞往城市 to_i 的航班，价格为 price_i。

你需要从城市 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 次中转以内（即乘坐最多 2 次航班），最便宜的路线是 0 -> 1 -> 2，总价格为 100 + 100 = 200。

解题过程

这是一个典型的带步数（跳跃次数/中转次数）限制的最短路径问题。它之所以是线性动态规划，是因为我们按步数（航班次数）来划分阶段，每个阶段的状态是“到达某个城市时的最小花费”。

第一步：定义状态

最直接的想法是定义二维 DP 数组：

• 设 dp[t][i] 表示恰好乘坐 t 次航班，到达城市 i 所需的最小花费。

但这里的“恰好”定义会带来初始化和转移的麻烦。更常用且方便的定义是：

• 设 dp[k][i] 表示最多经过 k 次中转（即最多乘坐 k+1 次航班），从起点 src 到达城市 i 所需的最小花费。

为什么用“最多经过 k 次中转”作为维度？
因为题目给出的限制 K 就是中转次数。k=0 表示不中转（直飞），k=K 就是我们要的最终答案可能存在的状态。

状态定义（最终采用）：
dp[k][v]：从 src 出发，最多经过 k 次中转，到达城市 v 所需的最小花费。
我们的目标是找到 dp[K][dst]。

第二步：确定初始状态

• 当你在起点，且尚未乘坐任何航班（中转次数 k 为任意值，但实际上我们从 k=0 开始递推）时，你就在起点 src，花费为 0。
• 对于其他城市，在开始时是无法到达的，我们用一个很大的数（比如无穷大 INF）来表示。

初始化：

INF = 10**9  # 一个足够大的数，表示不可达
# 创建一个二维数组 dp，维度为 (K+1) x n，因为 k 从 0 到 K
dp = [[INF] * n for _ in range(K+2)] # 多开一行方便统一转移
# 初始化：对于任何 k，如果我们还在起点 src，那么花费就是 0（还没起飞也算一种状态）
for k in range(K+2):
    dp[k][src] = 0

注意：这里 k 从 0 到 K+1 都初始化 dp[k][src] = 0，是因为即使允许的中转次数更多，在起点不动的花费依然是 0。但实际计算中，k=0 这一层是基础。

第三步：状态转移方程

我们如何计算 dp[k][v]？
要到达城市 v，并且最多经过 k 次中转，那么最后一次航班一定是从某个城市 u 飞过来的。

• 这次航班本身算作一次“乘坐”，它是否会消耗一次“中转”机会呢？
• 关键点：从 u 飞到 v 这次飞行，对于 v 而言，它消耗的“中转次数”限制，是看到达 u 时已经用了多少次中转。
• 因此，dp[k][v] 可以从所有能直达 v 的城市 u 转移而来，而 u 的状态是 dp[k-1][u]。因为从 src 到 u 最多用了 k-1 次中转，再加上 u->v 这趟航班，到达 v 时最多就用了 k 次中转。

所以状态转移方程为：
dp[k][v] = min(dp[k][v], dp[k-1][u] + price(u, v))，对于所有存在从 u 到 v 的航班，其价格为 price(u, v)。

通俗理解：要算出“最多转 k 次能到 v 的最便宜价格”，我们只需要遍历所有能飞到 v 的航班，看看“最多转 k-1 次能到该航班起点 u 的价格”加上本次航班价格，能不能刷新到 v 的价格。

第四步：计算顺序

• 外层循环：k 从 1 到 K+1。

  为什么是 K+1？因为 K 次中转意味着最多可以坐 K+1 次航班。我们的 dp 定义是“最多经过 k 次中转”，对应最多乘坐 k+1 次航班。为了找到乘坐 K+1 次航班（即中转 K 次）内的最优解，我们需要计算到 k = K 这一层。
  实际上，在循环中，k 代表的是“当前允许的最大中转次数”。我们从 k=1 开始，因为 k=0 这一层（不允许中转）可以通过初始化 dp[0][src]=0，并结合航班信息更新直飞航班得到。

更精确的循环：

1. 初始化 dp[0][src] = 0，其他为 INF。
2. 对于 k = 0, 1, 2, ..., K （共 K+1 层，代表最多中转 0, 1, ..., K 次）：
   • 对于每一个航班 (u, v, price)：
     • 如果 dp[k][u] 不是无穷大（意味着在最多 k 次中转内可以到达 u），那么我们就可以尝试从 u 乘坐这个航班去 v。
     • 这次飞行后，到达 v 时，中转次数最多为 k+1？不对，这里要小心。
     • 正确的转移：当我们处于 dp[k] 这一层时，它表示到达各个城市时最多已经用了 k 次中转。现在，我们利用这一层的信息去更新下一层 dp[k+1]。
     • 所以，对于航班 (u, v, w)，有：dp[k+1][v] = min(dp[k+1][v], dp[k][u] + w)

这样，我们从 k=0 开始，不断利用已知的“最多 k 次中转可达状态”，去推导“最多 k+1 次中转可达状态”。

第五步：答案

最终，我们想要的是“最多经过 K 次中转到达 dst”的最小花费，即 dp[K][dst]。
如果 dp[K][dst] 仍然是初始的 INF，说明在限制内无法到达，返回 -1。

第六步：举例演算

用之前的例子：n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, K=1
初始化 dp，大小为 (K+1+1) x n = 3 x 3，所有值设为 INF，且 dp[0][0] = 0。

初始 dp:
k=0: [0, INF, INF]
k=1: [0, INF, INF]
k=2: [0, INF, INF] (k=2对应最多中转1次？这里k是下标，我们最终看k=K=1那层)
我们需要更清晰的层次。定义 dp[k] 为最多 k 次中转。
那么 k 从 0 到 K。
初始化 dp[0][src]=0。

我们按定义重新清晰走一遍：

• dp[k][i]: 最多 k 次中转到达 i 的最小花费。k=0,1。
• 初始化: dp[0][0]=0, 其他 INF。
• 遍历航班更新：
  • k = 0 这层 (最多0次中转，即直飞):
    航班(0,1,100): 可以从 dp[0][0] 飞到1，花费 0+100=100。这会导致到达1时中转次数为0？是的，这是第一次飞行，不算中转。所以更新 dp[0][1] = min(INF, 100) = 100。
    航班(0,2,500): 更新 dp[0][2] = min(INF, 0+500)=500。
    航班(1,2,100): 此时 dp[0][1]=100 是有效的，所以可以从1飞到2，花费 100+100=200。但是，从1飞到2是第二次飞行，这算一次中转。所以这次飞行产生的结果应该更新到 k=1 那一层（因为现在到达2时，已经进行了一次中转）。
  • 所以我们需要两层循环嵌套:
    外层 for k in range(K+1): # k=0,1
    内层遍历所有航班 (u, v, w):
    如果 dp[k][u] != INF:
    dp[k+1][v] = min(dp[k+1][v], dp[k][u] + w)

让我们一步步模拟：
初始:
dp = [
[0, INF, INF], # k=0
[INF, INF, INF], # k=1
[INF, INF, INF] # k=2 (这一层我们可能用不到，但开了保险)
]
K=1

外层 k=0:
遍历航班:
(0,1,100): dp[0][0]=0 -> 更新 dp[1][1] = min(INF, 0+100)=100
(0,2,500): dp[0][0]=0 -> 更新 dp[1][2] = min(INF, 0+500)=500
(1,2,100): dp[0][1] 是 INF，不更新。
此时 dp 变为:
k=0: [0, INF, INF]
k=1: [INF, 100, 500]
k=2: [INF, INF, INF]

外层 k=1:
遍历航班:
(0,1,100): dp[1][0]=INF，不更新。
(0,2,500): dp[1][0]=INF，不更新。
(1,2,100): dp[1][1]=100 -> 更新 dp[2][2] = min(INF, 100+100)=200
此时 dp 变为:
k=0: [0, INF, INF]
k=1: [INF, 100, 500]
k=2: [INF, INF, 200]

我们需要的是 dp[K][dst] = dp[1][2]。在更新过程中，dp[1][2] 在 k=0 那轮被更新为 500。在 k=1 那轮，我们是用 dp[1][1] 更新了 dp[2][2]，并没有改变 dp[1][2]。
但题目要求“最多 K 次中转”，即 k <= K 都是可行的。所以最终答案应该是 min(dp[k][dst] for k in range(K+1))？不对，我们的定义 dp[k] 就是“最多 k 次中转”，所以 dp[K][dst] 本身就包含了中转次数小于等于 K 的所有可能中的最小值。在上面的例子中，dp[1][2] = 500 表示最多1次中转（即最多2次航班）到2的最小花费是500。但实际上我们有更便宜的200的路线（0->1->2），它出现在 dp[2][2]，这对应了最多2次中转？这里出现了不一致。

问题根源：我们的状态转移设计 dp[k+1][v] = min(dp[k+1][v], dp[k][u] + w) 意味着：要利用“最多 k 次中转到达 u”的状态，必须通过一次飞行 u->v，这次飞行一定会引入一次中转（除非 u 就是起点？不，从起点飞出的第一次飞行不算中转）。因此，这个转移方程实际上计算的是“恰好进行 k+1 次飞行到达 v 的最小花费”。但题目要求的是“最多 K 次中转”，即飞行次数 <= K+1。所以我们需要在最后取所有飞行次数 <= K+1 的结果中的最小值。

修正：我们可以改变状态定义，让 dp[k] 表示“恰好进行 k 次飞行”的最小花费。那么：
初始化 dp[0][src] = 0，表示进行0次飞行就在起点。
转移：dp[k][v] = min(dp[k][v], dp[k-1][u] + w) 对于所有航班 (u, v, w)。
最终答案：min(dp[t][dst] for t in range(1, K+2))，因为飞行次数 t 可以从 1 到 K+1。

按此修正重新演算上例：
定义 dp[t][i]：恰好乘坐 t 次航班到达 i 的最小花费。t=0,1,...,K+1。
初始化 dp[0][src]=0，其他 INF。

初始:
t=0: [0, INF, INF]
t=1: [INF, INF, INF]
t=2: [INF, INF, INF] (因为K=1，最多t=2)

遍历所有航班更新：
对于每个航班 (u, v, w)：
遍历 t 从 1 到 K+1 (1, 2):
如果 dp[t-1][u] != INF:
dp[t][v] = min(dp[t][v], dp[t-1][u] + w)

t=1:
(0,1,100): dp[0][0]=0 -> dp[1][1]=100
(0,2,500): dp[0][0]=0 -> dp[1][2]=500
(1,2,100): dp[0][1]=INF，不更新。
此时：
t=0: [0, INF, INF]
t=1: [INF, 100, 500]
t=2: [INF, INF, INF]

t=2:
(0,1,100): dp[1][0]=INF，不更新。
(0,2,500): dp[1][0]=INF，不更新。
(1,2,100): dp[1][1]=100 -> dp[2][2]=min(INF, 100+100)=200
此时：
t=0: [0, INF, INF]
t=1: [INF, 100, 500]
t=2: [INF, INF, 200]

最终，飞行次数 t 可以为 1 或 2。到达 dst=2 的最小花费是 min(dp[1][2], dp[2][2]) = min(500, 200) = 200。符合答案。

第七步：算法实现（Python）

def findCheapestPrice(n, flights, src, dst, K):
    INF = 10**9
    # dp[t][v]: 恰好乘坐 t 次航班到达城市 v 的最小花费
    # 我们需要 t 从 0 到 K+1
    dp = [[INF] * n for _ in range(K+2)]
    dp[0][src] = 0  # 0次航班就在起点

    for t in range(1, K+2):  # 乘坐航班次数
        dp[t] = dp[t-1][:]   # 初始化为上一轮的结果（这一步很重要，表示可以不飞满t次）
        for u, v, w in flights:
            if dp[t-1][u] != INF:
                dp[t][v] = min(dp[t][v], dp[t-1][u] + w)

    ans = min(dp[t][dst] for t in range(1, K+2))
    return ans if ans != INF else -1

# 测试示例
n = 3
flights = [[0,1,100],[1,2,100],[0,2,500]]
src = 0
dst = 2
K = 1
print(findCheapestPrice(n, flights, src, dst, K))  # 输出: 200

关键点：

1. dp[t] = dp[t-1][:] 这行代码是精髓。它意味着在计算“恰好 t 次航班”的最小花费时，我们先继承“恰好 t-1 次航班”的结果。因为题目求的是“最多 K 次中转”，相当于“最多 K+1 次航班”。如果能在少于 t 次航班内以更便宜的价格到达某个城市，这个信息需要保留。这行代码实际上让 dp[t][v] 变成了“最多乘坐 t 次航班到达 v 的最小花费”，简化了最后取最小值的步骤。
2. 转移时，我们只使用 dp[t-1] 来更新 dp[t]，保证了飞行次数的阶段递增。
3. 最终，dp[K+1][dst] 就已经是“最多乘坐 K+1 次航班（即最多 K 次中转）到达 dst”的最小花费了。

总结

这道题是线性动态规划中“带步数限制的最短路径”的典型应用。其核心在于：

1. 定义清晰的状态：以“恰好（或最多）乘坐的航班次数”为阶段，以“到达的城市”为状态。
2. 正确的转移：从上一航班次数的状态，通过已有的航班路线，更新当前航班次数的状态。
3. 巧妙的初始化与继承：通过 dp[t] = dp[t-1][:] 将“恰好”转化为“最多”，从而直接得到题目要求的答案。

通过按部就班的阶段推进，我们避免了图算法中可能因负权环或复杂限制带来的困难，清晰且高效地解决了问题。其时间复杂度为 O((K+1) * E)，其中 E 是航班数量，对于通常的题目规模非常可行。