🌟787. Cheapest Flights Within K Stops (M)

https://leetcode.com/problems/cheapest-flights-within-k-stops/

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

• 1 <= n <= 100

• 0 <= flights.length <= (n * (n - 1) / 2)

• flights[i].length == 3

• 0 <= fromi, toi < n

• fromi != toi

• 1 <= pricei <= 104

• There will not be any multiple flights between two cities.

• 0 <= src, dst, k < n

• src != dst

Solution:

本题目有三种解法： 1.BFS+Dijkstra 2.自顶向下的DFS 3.自底向上的DP

Version 1: Dijkstra

我们前文 BFS 算法框架详解 中说到，求最短路径，肯定可以用 BFS 算法来解决。

因为 BFS 算法相当于从起始点开始，一步一步向外扩散，那当然是离起点越近的节点越先被遍历到，如果 BFS 遍历的过程中遇到终点，那么走的肯定是最短路径。

不过呢，我们在 BFS 算法框架详解 用的是普通的队列 Queue 来遍历多叉树，而对于加权图的最短路径来说，普通的队列不管用了，得用优先级队列 PriorityQueue。

为什么呢？也好理解，在多叉树（或者扩展到无权图）的遍历中，与其说边没有权重，不如说每条边的权重都是 1，起点与终点之间的路径权重就是它们之间「边」的条数。

这样，按照 BFS 算法一步步向四周扩散的逻辑，先遍历到的节点和起点之间的「边」更少，累计的权重当然少。

换言之，先进入 Queue 的节点就是离起点近的，路径权重小的节点。

但对于加权图，路径中边的条数和路径的权重并不是正相关的关系了，有的路径可能边的条数很少，但每条边的权重都很大，那显然这条路径权重也会很大，很难成为最短路径。

比如题目给的这个例子：

你是可以一步从 0 走到 2，但路径权重不见得是最小的。

所以，对于加权图的场景，我们需要优先级队列「自动排序」的特性，将路径权重较小的节点排在队列前面，以此为基础施展 BFS 算法，也就变成了 Dijkstra 算法。

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    List<int[]>[] graph = new LinkedList[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : flights) {
        int from = edge[0];
        int to = edge[1];
        int price = edge[2];
        graph[from].add(new int[]{to, price});
    }

    // 启动 dijkstra 算法
    // 计算以 src 为起点在 k 次中转到达 dst 的最短路径
    K++;
    return dijkstra(graph, src, K, dst);
}

class State {
    // 图节点的 id
    int id;
    // 从 src 节点到当前节点的花费
    int costFromSrc;
    // 从 src 节点到当前节点经过的节点个数
    int nodeNumFromSrc;

    State(int id, int costFromSrc, int nodeNumFromSrc) {
        this.id = id;
        this.costFromSrc = costFromSrc;
        this.nodeNumFromSrc = nodeNumFromSrc;
    }
}

// 输入一个起点 src，计算从 src 到其他节点的最短距离
int dijkstra(List<int[]>[] graph, int src, int k, int dst) {
    // 定义：从起点 src 到达节点 i 的最短路径权重为 distTo[i]
    int[] distTo = new int[graph.length];
    // 定义：从起点 src 到达节点 i 至少要经过 nodeNumTo[i] 个节点
    int[] nodeNumTo = new int[graph.length];
    Arrays.fill(distTo, Integer.MAX_VALUE);
    Arrays.fill(nodeNumTo, Integer.MAX_VALUE);
    // base case
    distTo[src] = 0;
    nodeNumTo[src] = 0;

    // 优先级队列，costFromSrc 较小的排在前面
    Queue<State> pq = new PriorityQueue<>((a, b) -> {
        return a.costFromSrc - b.costFromSrc;
    });
    // 从起点 src 开始进行 BFS
    pq.offer(new State(src, 0, 0));

    while (!pq.isEmpty()) {
        State curState = pq.poll();
        int curNodeID = curState.id;
        int costFromSrc = curState.costFromSrc;
        int curNodeNumFromSrc = curState.nodeNumFromSrc;
        
        if (curNodeID == dst) {
            // 找到最短路径
            return costFromSrc;
        }
        if (curNodeNumFromSrc == k) {
            // 中转次数耗尽
            continue;
        }

        // 将 curNode 的相邻节点装入队列
        for (int[] neighbor : graph[curNodeID]) {
            int nextNodeID = neighbor[0];
            int costToNextNode = costFromSrc + neighbor[1];
            // 中转次数消耗 1
            int nextNodeNumFromSrc = curNodeNumFromSrc + 1;

             // 剪枝，如果中转次数更多，花费还更大，那必然不会是最短路径，否则会TLE
            if (costToNextNode > distTo[nextNodeID]
                && nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
                continue;
            }
            
            // 更新 dp table
            if (distTo[nextNodeID] > costToNextNode) {
                distTo[nextNodeID] = costToNextNode;
                nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
            }
           
            //注意这里是在if外面，跟普通模板的不同。
            //因为state还有一个node元素，不能只依靠dist判断是否进队列
            pq.offer(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
        }
    }
    return -1;
}

关于这个解法这里就不多解释了，可对照前文 Dijkstra 算法模板 理解。

Version 2: DFS

我们前文 动态规划核心套路详解 中说过，求最值的问题，很多都可能使用动态规划来求解。

加权最短路径问题，再加个 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];
}

备忘录初始值为啥初始为 -888？前文 base case 和备忘录的初始值怎么定 说过，随便初始化一个无意义的值就行。

至此，这道题就通过自顶向下的递归方式解决了。当然，完全可以按照这个解法衍生出自底向上迭代的动态规划解法，但由于篇幅所限，我就不写了，反正本质上都是一样的。

Version 3: DP

class Solution {
    int[][] memo;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        memo = new int[n+1][k+2];
        return dp(n, flights, src, dst, k+1);
    }
    public int dp(int n, int[][] flights, int src, int dst, int k){
        // base case
        if(k < 0){
            return -1;
        }else if(src == dst){
            return 0;
        }

        if(memo[src][k] != 0){
           return memo[src][k];
        }
        int res = Integer.MAX_VALUE;
        for(int[] f : flights){
            if(f[0] != src)
                continue;
            int subProblem = dp(n, flights, f[1], dst, k-1);
            if(subProblem == -1){
                continue;
            }
            res = Math.min(res, subProblem + f[2]);
        }

        memo[src][k] = res==Integer.MAX_VALUE?-1:res;
        return memo[src][k];
    }
}