共计 4458 个字符，预计需要花费 12 分钟才能阅读完成。
读完本文，能够去力扣解决如下题目：
787. K 站直达内最便宜的航班（Medium）
毕业季，对过来兴许有些欢畅和感伤，对将来兴许有些迷茫和向往，不过这些究竟是过眼云烟，迟早会被工夫淡化和忘记。
在这段美好时光的开端，的确应该来一场说走就走的毕业旅行，放肆一把，给青春画上一个完满的句号。
那么，本文就教给你一个动静布局算法，在毕业旅行中省钱，节约谋求诗和远方的资本。
假如，你筹备从学校所在的城市登程，游历多个城市，一路浪到公司入职，那么你应该如何安顿游览路线，能力最小化机票的开销？
咱们来看看力扣第 787 题「K 站直达内最便宜的航班」，我形容一下题目：
当初有 n 个城市，别离用 0,1…,n - 1 这些序号示意，城市之间的航线用三元组 [from, to, price] 来示意，比如说三元组 [0,1,100] 就示意，从城市 0 到城市 1 之间的机票价格是 100 元。
题目会给你输出若干参数：
正整数 n 代表城市个数，数组 flights 装着若干三元组代表城市间的航线及价格，城市编号 src 代表你所在的城市，城市编号 dst 代表你要去的指标城市，整数 K 代表你最多通过的中转站个数。
函数签名如下：
int findCheapestPrice(int n, int[][] flights, int src, int dst, int K);
请你的算法计算，在 K 次直达之内，从 src 到dst所需的最小破费是多少钱，如果无奈达到，则返回 -1。
比方说题目给的例子：
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, K = 0
航线就是如下这张图所示，有向边代表航线的方向，边上的数字代表航线的机票价格：
出发点是 0，达到点是2，容许的最大直达次数K 为 1，所以最小的开销就是图中红色的两条边，从 0 登程，通过直达城市 1 达到指标城市2，所以算法的返回值应该是 200。
留神这个直达次数的下限 K 是比拟辣手的，如果上述题目将 K 改为 0，也就是不容许直达，那么咱们的算法只能返回 500 了，也就是间接从 0 飞到2。
很显著，这题就是个加权有向图中求最短门路的问题。
说白了，就是给你一幅加权有向图，让你求 src 到dst权重最小的一条门路，同时要满足，这条门路最多不能超过 K + 1 条边 （通过K 个节点相当于通过 K + 1 条边。
咱们来剖析下求最短门路相干的算法。
BFS 算法思路
咱们前文 动静布局外围套路详解 中说过，求最值的问题，很多都可能应用动静布局来求解。
加权最短门路问题，再加个 K 的限度也不妨，不也是个求最值的问题嘛，动静布局通通拿下。
咱们先不论 K 的限度，单就「加权最短门路」这个问题来看看，它怎么就是个动静布局问题了呢？
比方说，当初我想计算 src 到dst的最短门路：
最小权重是多少？我不晓得。
但我能够把问题进行合成：
s1, s2是指向 dst 的相邻节点，它们之间的权重我是晓得的，别离是w1, w2。
只有我晓得了从 src 到s1, s2的最短门路，我不就晓得 src 到dst的最短门路了吗！
minPath(src, dst) = min(minPath(src, s1) + w1,
minPath(src, s2) + w2
)
这其实就是递归关系了，就是这么简略。
不过别忘了，题目对咱们的最短门路还有个「门路上不能超过 K + 1 条边」的限度。
那么咱们无妨定义这样一个 dp 函数：
int dp(int s, int k);
函数的定义如下：
从终点 src 登程，k步之内（一步就是一条边）达到节点 s 的最小门路权重为dp(s, k)。
那么，dp函数的 base case 就不言而喻了：
// 定义：从 src 登程，k 步之内达到 s 的最小老本
int dp(int s, int k) {
// 从 src 到 src，一步都不必走
if (s == src) {return 0;}
// 如果步数用尽，就无解了
if (k == 0) {return -1;}
// ...
}
题目想求的最小机票开销就能够用 dp(dst, K+1) 来示意：
int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// 将中转站个数转化成边的条数
K++;
//...
return dp(dst, K);
增加了一个 K 条边的限度，状态转移方程怎么写呢？其实和方才是一样的：
K步之内从 src 到dst的最小门路权重是多少？我不晓得。
但我能够把问题合成：
s1, s2是指向 dst 的相邻节点，我只有可能在 K - 1 步之内从 src 达到 s1, s2，那我就能够在K 步之内从 src 达到dst。
也就是如下关系式：
dp(dst, k) = min(dp(s1, k - 1) + w1,
dp(s2, k - 1) + w2
)
这就是新的状态转移方程，如果你能看懂这个算式，就曾经能够解决这道题了。
代码实现
根据上述思路，我怎么晓得 s1, s2 是指向 dst 的相邻节点，他们之间的权重是w1, w2？
我心愿给一个节点，就能晓得有谁指向这个节点，还晓得它们之间的权重，对吧。
业余点说，得用一个数据结构记录每个节点的「入度」indegree：
// 哈希表记录每个点的入度
// to -> [from, price]
HashMap<Integer, List<int[]>> indegree;
int src, dst;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// 将中转站个数转化成边的条数
K++;
this.src = src;
this.dst = dst;
indegree = new HashMap<>();
for (int[] f : flights) {int from = f[0];
int to = f[1];
int price = f[2];
// 记录谁指向该节点，以及之间的权重
indegree.putIfAbsent(to, new LinkedList<>());
indegree.get(to).add(new int[] {from, price});
}
return dp(dst, K);
}
有了 indegree 存储入度，那么就能够具体实现 dp 函数了：
// 定义：从 src 登程，k 步之内达到 s 的最短门路权重
int dp(int s, int k) {
// base case
if (s == src) {return 0;}
if (k == 0) {return -1;}
// 初始化为最大值，不便等会儿取最小值
int res = Integer.MAX_VALUE;
if (indegree.containsKey(s)) {
// 当 s 有入度节点时，合成为子问题
for (int[] v : indegree.get(s)) {int from = v[0];
int price = v[1];
// 从 src 达到相邻的入度节点所需的最短门路权重
int subProblem = dp(from, k - 1);
// 跳过无解的状况
if (subProblem != -1) {res = Math.min(res, subProblem + price);
}
}
}
// 如果还是初始值，阐明此节点不可达
return res == Integer.MAX_VALUE ? -1 : res;
}
有之前的铺垫，这段解法逻辑应该是很清晰的。当然，对于动静布局问题，必定要打消重叠子问题。
为什么有重叠子问题？很简略，如果某个节点同时指向两个其余节点，那么这两个节点就有雷同的一个入度节点，就会产生反复的递归计算。
怎么打消重叠子问题？找问题的「状态」。
状态是什么？在问题合成（状态转移）的过程中变动的，就是状态。
谁在变动？显然就是 dp 函数的参数 s 和k，每次递归调用，指标点 s 和步数束缚 k 在变动。
所以，本题的状态有两个，应该算是二维动静布局，咱们能够用一个 memo 二维数组或者哈希表作为备忘录，缩小反复计算。
咱们选用二维数组做备忘录吧，留神 K 是从 1 开始算的，所以备忘录初始大小要再加一：
int src, dst;
HashMap<Integer, List<int[]>> indegree;
// 备忘录
int[][] memo;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
K++;
this.src = src;
this.dst = dst;
// 初始化备忘录，全副填一个非凡值
memo = new int[n][K + 1];
for (int[] row : memo) {Arrays.fill(row, -888);
}
// 其余不变
// ...
return dp(dst, K);
}
// 定义：从 src 登程，k 步之内达到 s 的最小老本
int dp(int s, int k) {
// base case
if (s == src) {return 0;}
if (k == 0) {return -1;}
// 查备忘录，避免冗余计算
if (memo[s][k] != -888) {return memo[s][k];
}
// 状态转移不变
// ...
// 存入备忘录
memo[s][k] = res == Integer.MAX_VALUE ? -1 : res;
return memo[s][k];
}
查看更多优质算法文章 点击这里，手把手刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 90k star，欢送点赞！
