题目描述（Medium）
有 n
个城市通过一些航班连接。给你一个数组 flights
，其中 flights[i] = [fromi, toi, pricei]
，表示该航班都从城市 fromi
开始，以价格 toi
抵达 pricei
。
现在给定所有的城市和航班，以及出发城市 src
和目的地 dst
，你的任务是找到出一条最多经过 k
站中转的路线，使得从 src
到 dst
的 价格最便宜 ，并返回该价格。如果不存在这样的路线，则输出 -1
。
示例 1：
输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 输出: 200 解释: 城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
示例 2：
输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 输出: 500 解释: 城市航班图如下
提示：
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
方法一、记忆化搜索
本题显然是可以使用DFS来做的，只需要把从 src 到 dst 的所有路径搜索一遍即可，但是，当用例非常大时，有可能超时，所以，我们需要加上记忆化，对于搜索过的路径，从缓存中拿过来使用即可。
加记忆化的过程也比较简单，就是找到你的 dfs 函数参数中变的部分即可，比如，我们下面的代码中，变的部分就是 i 和 k，所以，声明一个 memo 数组记录已经遍历过的节点。
代码如下，比较简单，注意边界及返回值：
class Solution {
int INF = 1000007;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// k表示经过的节点，我们转成边数（步数），这样好计算一些
int[][] memo = new int[n][k+2];
int ans = dfs(flights, src, dst, k + 1, memo);
return ans >= INF ? -1 : ans;
}
// 表示从 i 到 dst 的走 k 步的最小价格
private int dfs(int[][] flights, int i, int dst, int k, int[][] memo) {
if (k < 0) {
return INF;
}
if (i == dst) {
return 0;
}
if (memo[i][k] != 0) {
return memo[i][k];
}
int min = INF;
for (int[] flight : flights) {
// 遍历 i 的下一个节点
if (flight[0] == i) {
min = Math.min(min, dfs(flights, flight[1], dst, k - 1, memo) + flight[2]);
}
}
memo[i][k] = min;
return min;
}
}
时间复杂度：，题目给定的 的范围为，与 成正比，我们这里要遍历 层，每层都需要遍历一遍 数组。 空间复杂度：， 数组占用 的额外空间，递归栈占用 的额外空间。
运行结果如下：
方法二、动态规划
有了记忆化搜索，转成动态规划就比较简单了，我们可以这样定义动态规划：
状态定义： dp[i][k]
表示从i
点到dst
走k
步的最少价格状态转移：，其中 为 的下一个节点 初始值：初始时，dst 到 dst 走 0 步的最少价格为 0，其它为无穷大 返回值：取 中的最小值即可
好了，请看代码：
class Solution {
int INF = 1000007;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
return dp(n, flights, src, dst, k);
}
private int dp(int n, int[][] flights, int src, int dst, int K) {
// dp[i][k]表示从i点到dst走k步的最少价格
// dp[i][k]=min(dp[i_next][k-1] + g[i][j])
int[][] dp = new int[n][K+2];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], INF);
}
dp[dst][0] = 0;
for (int k = 1; k <= K + 1; k++) {
for (int[] flight : flights) {
dp[flight[0]][k] = Math.min(dp[flight[0]][k], dp[flight[1]][k - 1] + flight[2]);
}
}
int ans = IntStream.of(dp[src]).min().getAsInt();
return ans >= INF ? -1 : ans;
}
}
时间复杂度：，题目给定的 的范围为，与 成正比，我们这里要遍历 次，每次都需要遍历一遍 数组。 空间复杂度：， 数组占用 的额外空间。
运行结果如下：
方法三、动态数组 + 优化
可以看到，方法二中， 只与 有关，所以，我们可以使用滚动数组来优化空间。
所谓滚动数组，即申请一个两行的数组，轮动使用，计算当前行为 ，上一行就是 ， 根据你的变量变化。
请看代码：
class Solution {
int INF = 1000007;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
return dp(n, flights, src, dst, k);
}
private int dp(int n, int[][] flights, int src, int dst, int K) {
// dp[i][k]表示从i点到dst走k步的最少价格
// dp[i][k]=min(dp[i_next][k-1] + g[i][j])
int ans = INF;
int[][] dp = new int[2][n];
Arrays.fill(dp[0], INF);
dp[0][dst] = 0;
for (int k = 1; k <= K + 1; k++) {
// 防止之前的值干扰，每次都要初始化
Arrays.fill(dp[k & 1], INF);
for (int[] flight : flights) {
dp[k & 1][flight[0]] = Math.min(dp[k & 1][flight[0]], dp[(k - 1) & 1][flight[1]] + flight[2]);
}
ans = Math.min(ans, dp[k & 1][src]);
}
return ans >= INF ? -1 : ans;
}
}
时间复杂度：，题目给定的 的范围为，与 成正比，我们这里要遍历 次，每次都需要遍历一遍 数组。 空间复杂度：， 数组占用 的额外空间。
运行结果如下：
方法四、BFS + 剪枝
既然是求最短路径，我们使用 BFS 也是可以的，不过，考虑到用例非常大的情况，我们需要认真的思考剪枝的方案，本题我们申请一个 数组记录从 src 到 i 的最小价格，下次再遍历到 i 时，如果价格比记录的值小才计算，否则直接丢弃。
请看代码：
class Solution {
int INF = 1000007;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
return bfs(n, flights, src, dst, k);
}
private int bfs(int n, int[][] flights, int src, int dst, int k) {
// 整理题目给定的flights，转换成每个节点的子节点有哪些
List<int[]>[] g = new List[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int[] flight : flights) {
g[flight[0]].add(new int[] {flight[1], flight[2]});
}
// 表示src到i到最小价格
int[] ans = new int[n];
Arrays.fill(ans, INF);
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {src, 0});
// 退出条件加上 k 的限制
while (!queue.isEmpty() && k + 1 > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] poll = queue.poll();
for (int[] path : g[poll[0]]) {
int distance = poll[1] + path[1];
// 剪枝1，小于 i 之前记录的最小值，且小于 dst 之前记录的最小值
if (distance < ans[path[0]] && distance < ans[dst]) {
ans[path[0]] = distance;
// 剪枝2，到 dst 了就不用继续往下了
if (path[0] != dst) {
queue.offer(new int[] {path[0], distance});
}
}
}
}
k--;
}
return ans[dst] >= INF ? -1 : ans[dst];
}
}
时间复杂度：，最多遍历 K 层，每层最多有 n-1 个元素，每个元素最多有 n-1 个子节点。 空间复杂度：，、、 数组最多只占用 的额外空间。
运行结果如下：
最后
如果对你有帮助，请点个赞吧，谢谢^^
也可以关注我的公号【彤哥来刷题啦】，每日分享题解，一起刷题，一起拿全家桶。
