旅游省钱大法：加权最短路径

787. K 站中转内最便宜的航班 https://leetcode.cn/problems/cheapest-flights-within-k-stops

787. Cheapest Flights Within K Stops https://leetcode.com/problems/cheapest-flights-within-k-stops

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
787. Cheapest Flights Within K Stops	🟠

Prerequisites

Before reading this article, you should learn:

• Graph Structure Basics
• Graph Traversal
• Dynamic Programming Core Framework

Graduation season is a time of mixed emotions—joy and nostalgia for the past, uncertainty and anticipation for the future. However, these feelings are transient and will eventually fade with time.

As this wonderful period comes to an end, it's the perfect time for a spontaneous graduation trip to let loose and give your youth a perfect conclusion.

In this article, I'll teach you a dynamic programming algorithm to save money on your graduation trip, preserving more capital for your pursuit of poetry and distant horizons.

Imagine you're starting from your school's city and planning to visit multiple cities before finally arriving at your company for your new job. How should you plan your travel route to minimize airfare costs?

Let's take a look at LeetCode problem #787, "Cheapest Flights Within K Stops":

787. Cheapest Flights Within K Stops | 力扣 | LeetCode |

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 = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

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 above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

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 above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

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

The function signature is as follows:

java 🟢

int findCheapestPrice(int n, int[][] flights, int src, int dst, int K);

cpp 🤖

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K);

python 🤖

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:

go 🤖

func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {}

javascript 🤖

var findCheapestPrice = function(n, flights, src, dst, K) {}

Clearly, this problem is about finding the shortest path in a weighted directed graph.

In simple terms, you are given a weighted directed graph and asked to find the path from src to dst with the minimum weight. Additionally, this path must not exceed K + 1 edges (passing through K nodes is equivalent to passing through K + 1 edges).

Let's analyze the algorithms related to finding the shortest path.

BFS Algorithm Approach

In our previous article BFS Algorithm Framework Explained, we mentioned that BFS can be used to find the shortest path.

This is because BFS starts from the initial point and spreads out step by step. Naturally, nodes closer to the starting point are visited first. If the destination is encountered during BFS traversal, the path taken is guaranteed to be the shortest.

However, in BFS Algorithm Framework Explained, we used a regular queue Queue to traverse a multi-tree. For the shortest path in a weighted graph, a regular queue won't suffice; we need a priority queue PriorityQueue.

Why? It's understandable. In the traversal of a multi-tree (or extending to an unweighted graph), it's not that the edges have no weight, but rather that each edge has a weight of 1. The path weight between the start and end points is simply the number of edges between them.

Thus, following the BFS logic of spreading out step by step, nodes visited earlier have fewer edges between them and the start, resulting in a smaller cumulative weight.

In other words, nodes that enter the Queue first are closer to the start and have a smaller path weight.

For weighted graphs, however, the number of edges in a path is not directly correlated with the path's weight. Some paths may have fewer edges, but each edge may have a high weight, making the overall path weight large and unlikely to be the shortest.

For example, consider this scenario given in the problem:

You can move from 0 to 2 in one step, but the path weight might not be the smallest.

Therefore, for weighted graphs, we need the "automatic sorting" feature of the priority queue to keep nodes with smaller path weights at the front. This approach, combined with BFS, transforms into the Dijkstra Algorithm.

Having discussed the BFS approach, it's to help you understand the concept. In this article, we will mainly focus on how to use dynamic programming to solve this problem. The implementation code for Dijkstra's algorithm is provided at the end for reference.

Dynamic Programming Approach

In our previous article Dynamic Programming Core Techniques Explained, we mentioned that many problems involving finding the maximum or minimum value can be solved using dynamic programming.

The weighted shortest path problem, even with an additional K constraint, is still a problem of finding the extremum. Dynamic programming can handle it all.

Let's first ignore the K constraint and focus on the "weighted shortest path" problem. Why is it a dynamic programming problem?

For example, suppose I want to calculate the shortest path from src to dst:

What is the minimum weight? I don't know.

But I can break down the problem:

s1, s2 are adjacent nodes leading to dst. I know the weights between them, which are w1, w2.

As long as I know the shortest paths from src to s1, s2, I can determine the shortest path from src to dst!

minPath(src, dst) = min(
    minPath(src, s1) + w1, 
    minPath(src, s2) + w2
)

This is essentially a recursive relationship, and it's that simple.

However, don't forget that the problem also imposes a constraint that the shortest path "cannot exceed K + 1 edges."

So, let's define a dp function like this:

java 🟢

int dp(int s, int k);

cpp 🤖

int dp(int s, int k);

python 🤖

def dp(s: int, k: int) -> int:

go 🤖

func dp(s int, k int) int {}

javascript 🤖

var dp = function(s, k) {}

The function is defined as follows:

Starting from the source node src, the minimum path weight to reach node s within k steps (one step equals one edge) is dp(s, k).

Therefore, the base case for the dp function is straightforward:

java 🟢

// Definition: the minimum cost to reach s within k steps starting from src
int dp(int s, int k) {
    // From src to src, no steps are needed
    if (s == src) {
        return 0;
    }
    // If the number of steps is exhausted, there is no solution
    if (k == 0) {
        return -1;
    }

    // ...
}

cpp 🤖

// Definition: the minimum cost to reach s within k steps starting from src
int dp(int s, int k) {
    // From src to src, no steps are needed
    if (s == src) {
        return 0;
    }
    // If the number of steps is exhausted, there is no solution
    if (k == 0) {
        return -1;
    }

    // ...
}

python 🤖

# Definition: the minimum cost to reach s from src within k steps
def dp(s: int, k: int) -> int:
    # From src to src, no steps are needed
    if s == src:
        return 0
    # If the number of steps is exhausted, there is no solution
    if k == 0:
        return -1

    # ...

go 🤖

// Definition: the minimum cost to reach s within k steps starting from src
func dp(s, k int) int {
    // From src to src, no steps are needed
    if s == src {
        return 0
    }
    // If the number of steps is exhausted, there is no solution
    if k == 0 {
        return -1
    }

    // ...
}

javascript 🤖

// Definition: The minimum cost to reach s from src within k steps
var dp = function(s, k) {
    // From src to src, no steps are needed
    if (s === src) {
        return 0;
    }
    // If the number of steps is exhausted, there is no solution
    if (k === 0) {
        return -1;
    }

    // ...
}

The minimum flight cost the problem seeks can be represented as dp(dst, K+1):

java 🟢

int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    // convert the number of transit stops into the number of edges
    K++;
    // ...
    return dp(dst, K);
}

cpp 🤖

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    // convert the number of transit stops into the number of edges
    K++;
    // ...
    return dp(dst, K);
}

python 🤖

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    # convert the number of transit stops into the number of edges
    K += 1
    #...
    return dp(dst, K)

go 🤖

func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {
    // convert the number of transit stops into the number of edges
    K++
    // ...
    return dp(dst, K)
}

javascript 🤖

var findCheapestPrice = function(n, flights, src, dst, K) {
    // convert the number of transit stops into the number of edges
    K++;
    // ...
    return dp(dst, K);
};

When adding a constraint of K edges, how do we write the state transition equation? It's actually the same as before:

What is the minimum path weight from src to dst within K steps? I don't know.

But I can break down the problem:

s1, s2 are the adjacent nodes pointing to dst. If I know the minimum path from src to s1, s2 within K - 1 steps, then I can reach dst from src within K steps.

This can be expressed as the following relationship:

dp(dst, k) = min(
    dp(s1, k - 1) + w1, 
    dp(s2, k - 1) + w2
)

This is the new state transition equation. If you can understand this formula, you can already solve this problem.

Code Implementation

Based on the above approach, how do I know that s1, s2 are adjacent nodes pointing to dst, with weights w1, w2 between them?

I want to know which nodes point to a given node and also know the weights between them, right?

To put it professionally, we need a data structure to record the "indegree" of each node, which stores all adjacent nodes pointing to the node and the weights of the edges between them.

Let's look at the code. We use a hash table indegree to store the indegree and then implement the dp function:

java 🟢

class Solution {
    // Hash table to record the indegree of each node, where the key is the node number and the value is the adjacent nodes pointing to this node along with their weights
    // to -> [from, price]
    HashMap<Integer, List<int[]>> indegree;
    int src, dst;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        // Convert the number of transit stations into the number of edges
        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];
            // Record which node points to this node and the weight between them
            indegree.putIfAbsent(to, new LinkedList<>());
            indegree.get(to).add(new int[] {from, price});
        }
        
        return dp(dst, K);
    }

    // Definition: the shortest path weight from src to s within k steps
    int dp(int s, int k) {
        // base case
        if (s == src) {
            return 0;
        }
        if (k == 0) {
            return -1;
        }
        // Initialize to the maximum value for easy minimum value extraction later
        int res = Integer.MAX_VALUE;
        if (indegree.containsKey(s)) {
            // When s has indegree nodes, decompose into subproblems
            for (int[] v : indegree.get(s)) {
                int from = v[0];
                int price = v[1];
                // The shortest path weight required to reach the adjacent indegree node from src
                int subProblem = dp(from, k - 1);

                // Skip cases where there is no solution
                if (subProblem != -1) {
                    res = Math.min(res, subProblem + price);
                }
            }
        }
        // If it is still the initial value, it means this node is unreachable
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

cpp 🤖

class Solution {
public:
    // Hash table to record the indegree of each point, key is the node number, value is the adjacent nodes pointing to this node and the weight between them
    // to -> [from, price]
    unordered_map<int, vector<pair<int, int>>> indegree;
    int src, dst;
    
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        // Convert the number of transit stations to the number of edges
        K++;
        this->src = src;
        this->dst = dst;
        
        for(const auto& f : flights) {
            int from = f[0];
            int to = f[1];
            int price = f[2];
            // Record who points to this node and the weight between them
            indegree[to].push_back(make_pair(from, price));
        }
        
        return dp(dst, K);
    }
    
    // Definition: the shortest path weight from src to s within k steps
    int dp(int s, int k) {
        // base case
        if (s == src) {
            return 0;
        }
        if (k == 0) {
            return -1;
        }
        // Initialize to the maximum value for easy minimum value extraction later
        int res = INT_MAX;
        if (indegree.count(s)) {
            // When s has indegree nodes, decompose into subproblems
            for(const auto& v : indegree[s]) {
                int from = v.first;
                int price = v.second;
                // The shortest path weight required to reach the adjacent indegree node from src
                int subProblem = dp(from, k - 1);

                // Skip unsolvable cases
                if (subProblem != -1) {
                    res = min(res, subProblem + price);
                }
            }
        }
        // If it is still the initial value, it means this node is unreachable
        return res == INT_MAX ? -1 : res;
    }
};

python 🤖

class Solution:
    def __init__(self):
        # Hash table to record the indegree of each node, key is the node number, value is the adjacent nodes pointing to this node and the weight between them
        # to -> [from, price]
        self.indegree = {}
        self.src = 0
        self.dst = 0

    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        # Convert the number of transit stations to the number of edges
        K += 1
        self.src = src
        self.dst = dst
        
        for f in flights:
            from_, to, price = f
            # Record which node points to this node and the weight between them
            if to not in self.indegree:
                self.indegree[to] = []
            self.indegree[to].append([from_, price])
        
        return self.dp(dst, K)
    
    # Definition: the shortest path weight from src to s within k steps
    def dp(self, s: int, k: int) -> int:
        # base case
        if s == self.src:
            return 0
        if k == 0:
            return -1
        # Initialize to the maximum value for easy minimum value extraction later
        res = float('inf')
        if s in self.indegree:
            # When s has indegree nodes, decompose into subproblems
            for v in self.indegree[s]:
                from_, price = v
                # The shortest path weight required to reach the adjacent indegree node from src
                subProblem = self.dp(from_, k - 1) 

                # Skip unsolvable cases
                if subProblem != -1:
                    res = min(res, subProblem + price)
        # If it is still the initial value, it means this node is unreachable
        return -1 if res == float('inf') else res

go 🤖

func findCheapestPrice(n int, flights [][]int, src, dst, K int) int {
    // Hash table to record the indegree of each node, key is the node number, value is the adjacent nodes pointing to this node and the weight between them
    // to -> [from, price]
    indegree := make(map[int][][2]int)
    // Convert the number of transit stations to the number of edges
    K++
    for _, f := range flights {
        from, to, price := f[0], f[1], f[2]
        // Record which node points to this node and the weight between them
        indegree[to] = append(indegree[to], [2]int{from, price})
    }

    return dp(src, dst, K, indegree)
}

// Definition: the minimum cost to reach s within k steps starting from src
func dp(src, s, k int, indegree map[int][][2]int) int {
    // base case
    if s == src {
        return 0
    }
    if k == 0 {
        return -1
    }
    // Initialize to the maximum value for easy minimum value extraction later
    res := math.MaxInt32
    if v, ok := indegree[s]; ok {
        // When s has indegree nodes, decompose into subproblems
        for _, p := range v {
            from, price := p[0], p[1]
            // The shortest path weight required to reach the adjacent indegree node from src
            subProblem := dp(src, from, k - 1, indegree)

            // Skip unsolvable cases
            if subProblem != -1 {
                res = min(res, subProblem + price)
            }
        }
    }
    // If it is still the initial value, it means this node is unreachable
    if res == math.MaxInt32 {
        return -1
    }
    return res
}

javascript 🤖

var findCheapestPrice = function(n, flights, src, dst, K) {
    // Hash table to record the indegree of each node, where the key is the node number and the value is the adjacent nodes pointing to this node along with the weights
    // to -> [from, price]
    let indegree = new Map();
    // Convert the number of transit stops into the number of edges
    K++;
    for (let f of flights) {
        let from = f[0];
        let to = f[1];
        let price = f[2];
        // Record which node points to this node and the weight between them
        if (!indegree.has(to)) {
            indegree.set(to, []);
        }
        indegree.get(to).push([from, price]);
    }

    return dp(src, dst, K, indegree);
};

// Definition: the minimum cost to reach s from src within k steps
var dp = function(src, s, k, indegree) {
    // base case
    if (s === src) {
        return 0;
    }
    if (k === 0) {
        return -1;
    }
    // Initialize to the maximum value for easy minimum value extraction later
    let res = Infinity;
    if (indegree.has(s)) {
        // When s has indegree nodes, decompose into subproblems
        for (let v of indegree.get(s)) {
            let from = v[0];
            let price = v[1];
            // The shortest path weight required to reach the adjacent indegree node from src
            let subProblem = dp(src, from, k - 1, indegree);

            // Skip unsolvable cases
            if (subProblem !== -1) {
                res = Math.min(res, subProblem + price);
            }
        }
    }
    // If it is still the initial value, it means this node is unreachable
    return res === Infinity ? -1 : res;
};

With the previous foundation, the logic of this solution should be quite clear. Of course, for dynamic programming problems, overlapping subproblems must be eliminated.

Why are there overlapping subproblems? It's simple. If a node points to two other nodes, these two nodes share a common incoming node, leading to repeated recursive calculations.

How to eliminate overlapping subproblems? Identify the "state" of the problem.

What is a state? It's what changes during the problem decomposition (state transition) process.

What changes? Obviously, it's the parameters s and k of the dp function. With each recursive call, the target point s and the step constraint k change.

Therefore, this problem has two states, making it a two-dimensional dynamic programming problem. We can use a two-dimensional array memo or a hash table as a memoization tool to reduce redundant calculations.

Let's use a two-dimensional array for memoization. Note that K starts from 1, so the initial size of the memoization array needs to be incremented by one:

java 🟢

class Solution {
    int src, dst;
    HashMap<Integer, List<int[]>> indegree;
    // memoization
    int[][] memo;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        K++;
        this.src = src;
        this.dst = dst;
        // initialize the memoization table with a special value
        memo = new int[n][K + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -888);
        }
        
        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);
    }

    // definition: the minimum cost to reach s from src within k steps
    int dp(int s, int k) {
        // base case
        if (s == src) {
            return 0;
        }
        if (k == 0) {
            return -1;
        }
        // check the memoization table to prevent redundant calculations
        if (memo[s][k] != -888) {
            return memo[s][k];
        }
        
        // state transition code remains unchanged
        int res = Integer.MAX_VALUE;
        if (indegree.containsKey(s)) {
            for (int[] v : indegree.get(s)) {
                int from = v[0];
                int price = v[1];
                int subProblem = dp(from, k - 1);

                if (subProblem != -1) {
                    res = Math.min(res, subProblem + price);
                }
            }
        }
        // store in the memoization table
        memo[s][k] = res == Integer.MAX_VALUE ? -1 : res;
        return memo[s][k];
    }
}

cpp 🤖

class Solution {
    int src, dst;
    unordered_map<int, vector<vector<int>>> indegree;
    // memoization
    vector<vector<int>> memo;

public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        K++;
        this->src = src;
        this->dst = dst;
        // initialize the memoization, fill all with a special value
        memo = vector<vector<int>>(n, vector<int>(K + 1, -888));
        
        for(const auto& f : flights) {
            int from = f[0];
            int to = f[1];
            int price = f[2];
            indegree[to].push_back({from, price});
        }
        
        return dp(dst, K);
    }

    // definition: the minimum cost to reach s within k steps starting from src
    int dp(int s, int k) {
        // base case
        if (s == src) {
            return 0;
        }
        if (k == 0) {
            return -1;
        }
        // check the memoization to prevent redundant calculations
        if (memo[s][k] != -888) {
            return memo[s][k];
        }
        
        // state transition code remains unchanged
        int res = INT_MAX;
        if (indegree.count(s)) {
            for(const auto& v : indegree[s]) {
                int from = v[0];
                int price = v[1];
                int subProblem = dp(from, k - 1);

                if (subProblem != -1) {
                    res = min(res, subProblem + price);
                }
            }
        }
        // store in memoization
        memo[s][k] = res == INT_MAX ? -1 : res;
        return memo[s][k];
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.src = 0
        self.dst = 0
        self.indegree = {}
        # memoization
        self.memo = []

    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        K += 1
        self.src = src
        self.dst = dst
        # initialize the memoization with a special value
        self.memo = [[-888] * (K + 1) for _ in range(n)]
        
        for f in flights:
            from_, to, price = f
            if to not in self.indegree:
                self.indegree[to] = []
            self.indegree[to].append([from_, price])
        
        return self.dp(dst, K)
    
    # definition: the minimum cost to reach s from src within k steps
    def dp(self, s: int, k: int) -> int:
        # base case
        if s == self.src:
            return 0
        if k == 0:
            return -1
        # check the memoization to prevent redundant calculations
        if self.memo[s][k] != -888:
            return self.memo[s][k]
        
        # the state transition code remains unchanged
        res = float('inf')
        if s in self.indegree:
            for v in self.indegree[s]:
                from_, price = v
                subProblem = self.dp(from_, k - 1) 

                if subProblem != -1:
                    res = min(res, subProblem + price)
        # store in the memoization
        self.memo[s][k] = -1 if res == float('inf') else res
        return self.memo[s][k]

go 🤖

func findCheapestPrice(n int, flights [][]int, src, dst, K int) int {
    indegree := make(map[int][][2]int)
    K++
    // initialize the memoization table with a special value
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, K + 1)
        for j := range memo[i] {
            memo[i][j] = -888
        }
    }

    for _, f := range flights {
        from, to, price := f[0], f[1], f[2]
        indegree[to] = append(indegree[to], [2]int{from, price})
    }

    return dp(src, dst, K, indegree, memo)
}

// definition: the minimum cost to reach s from src within k steps
func dp(src, s, k int, indegree map[int][][2]int, memo [][]int) int {
    // base case
    if s == src {
        return 0
    }
    if k == 0 {
        return -1
    }
    // check the memoization table to prevent redundant calculations
    if memo[s][k] != -888 {
        return memo[s][k]
    }
    
    // the state transition code remains unchanged
    res := math.MaxInt32
    if v, ok := indegree[s]; ok {
        for _, p := range v {
            from, price := p[0], p[1]
            subProblem := dp(src, from, k - 1, indegree, memo)
            if subProblem != -1 {
                res = min(res, subProblem + price)
            }
        }
    }
    // store in the memoization table
    if res == math.MaxInt32 {
        memo[s][k] = -1
    } else {
        memo[s][k] = res
    }
    return memo[s][k]
}

javascript 🤖

var findCheapestPrice = function(n, flights, src, dst, K) {
    let indegree = new Map();
    K++;
    // initialize the memoization table, fill all with a special value
    let memo = new Array(n).fill(0).map(() => new Array(K + 1).fill(-888));

    for (let f of flights) {
        let from = f[0];
        let to = f[1];
        let price = f[2];
        if (!indegree.has(to)) {
            indegree.set(to, []);
        }
        indegree.get(to).push([from, price]);
    }

    return dp(src, dst, K, indegree, memo);
};

// definition: the minimum cost to reach s from src within k steps
var dp = function(src, s, k, indegree, memo) {
    // base case
    if (s === src) {
        return 0;
    }
    if (k === 0) {
        return -1;
    }
    // check the memoization table to prevent redundant calculations
    if (memo[s][k] !== -888) {
        return memo[s][k];
    }
    
    // state transition code remains unchanged
    let res = Infinity;
    if (indegree.has(s)) {
        for (let v of indegree.get(s)) {
            let from = v[0];
            let price = v[1];
            let subProblem = dp(src, from, k - 1, indegree, memo);
            if (subProblem !== -1) {
                res = Math.min(res, subProblem + price);
            }
        }
    }
    // store in the memoization table
    memo[s][k] = res === Infinity ? -1 : res;
    return memo[s][k];
};

Why is the initial value of the memo set to -888? As mentioned in the previous article How to Determine Base Cases and Initial Values for Memoization, you can initialize it with any meaningless value.

With this, the problem is solved using a top-down recursive approach. Of course, you can derive a bottom-up iterative dynamic programming solution from this approach, but due to space limitations, I won't write it out. Essentially, they are the same.

Actually, if you read all the previous articles on dynamic programming, you'll notice that we've been consistently applying the Core Pattern of Dynamic Programming. It's really not that difficult.

Lastly, to expand on this, some readers might wonder: since this problem is essentially about graph traversal, why don't we need a visited set to record the nodes that have already been visited?

I discussed this question in the Dijkstra Algorithm Template, so you can check that out. Additionally, this problem can also be solved using the Dijkstra algorithm template, and the code is as follows:

java 🟢

class Solution {
    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});
        }

        // start the Dijkstra algorithm
        // calculate the shortest path from src to dst with at most k transfers
        K++;
        return dijkstra(graph, src, K, dst);
    }

    class State {
        // the id of the graph node
        int id;
        // the cost from src node to the current node
        int costFromSrc;
        // the number of nodes passed from src to the current node
        int nodeNumFromSrc;

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

    // input a starting point src, calculate the shortest distance from src to other nodes
    int dijkstra(List<int[]>[] graph, int src, int k, int dst) {
        // define: the shortest path weight from src to node i is distTo[i]
        int[] distTo = new int[graph.length];
        // define: the minimum weight path from src to node i must pass through at least nodeNumTo[i] nodes
        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;

        // priority queue, where nodes with smaller costFromSrc come first
        Queue<State> pq = new PriorityQueue<>((a, b) -> {
            return a.costFromSrc - b.costFromSrc;
        });
        // start BFS from the starting point src
        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) {
                // found the shortest path
                return costFromSrc;
            }
            if (curNodeNumFromSrc == k) {
                // the number of transfers is exhausted
                continue;
            }

            // add the neighbors of curNode to the queue
            for (int[] neighbor : graph[curNodeID]) {
                int nextNodeID = neighbor[0];
                int costToNextNode = costFromSrc + neighbor[1];
                // consume 1 transfer
                int nextNodeNumFromSrc = curNodeNumFromSrc + 1;

                // update the dp table
                if (distTo[nextNodeID] > costToNextNode) {
                    distTo[nextNodeID] = costToNextNode;
                    nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
                }
                // pruning, if the number of transfers is higher and the cost is also higher, it cannot be the shortest path
                if (costToNextNode > distTo[nextNodeID]
                    && nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
                    continue;
                }
                
                pq.offer(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
            }
        }
        return -1;
    }
}

cpp 🤖

class Solution {
public:
    struct State {
        // ID of the graph node
        int id;
        // Cost from src node to the current node
        int costFromSrc;
        // Number of nodes passed from src node to the current node

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

    // Custom comparator to prioritize elements with smaller costFromSrc in the priority queue
    class CompareState {
    public:
        bool operator()(State const& s1, State const& s2) {
            return s1.costFromSrc > s2.costFromSrc;
        }
    };

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int*>> graph(n);
        for (vector<int> edge : flights) {
            int from = edge[0];
            int to = edge[1];
            int price = edge[2];
            int* arr = new int[2]{to, price};
            graph[from].push_back(arr);
        }

        // Start Dijkstra's algorithm
        // Calculate the shortest path from src to dst with at most k transfers
        K++;
        return dijkstra(graph, src, K, dst);
    }

    int dijkstra(vector<vector<int*>>& graph, int src, int k, int dst) {
        // Definition: The shortest path weight from src to node i is distTo[i]
        vector<int> distTo(graph.size(), INT_MAX);
        // Definition: The minimum weight path from src to node i must pass through at least nodeNumTo[i] nodes
        vector<int> nodeNumTo(graph.size(), INT_MAX);
        // base case
        distTo[src] = 0;
        nodeNumTo[src] = 0;

        // Priority queue, elements with smaller costFromSrc are prioritized
        priority_queue<State, vector<State>, CompareState> pq;
        // Start BFS from the src node
        pq.push(State(src, 0, 0));
        while (!pq.empty()) {
            State curState = pq.top();
            pq.pop();
            int curNodeID = curState.id;
            int costFromSrc = curState.costFromSrc;
            int curNodeNumFromSrc = curState.nodeNumFromSrc;

            if (curNodeID == dst) {
                // Found the shortest path
                return costFromSrc;
            }
            if (curNodeNumFromSrc == k) {
                // Transfer count exhausted
                continue;
            }
            // Add adjacent nodes of the current node to the queue
            for (int* neighbor : graph[curNodeID]) {
                int nextNodeID = neighbor[0];
                int costToNextNode = costFromSrc + neighbor[1];
                // Transfer count decreases by 1
                int nextNodeNumFromSrc = curNodeNumFromSrc + 1;

                // Update dp table
                if (distTo[nextNodeID] > costToNextNode) {
                    distTo[nextNodeID] = costToNextNode;
                    nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
                }
                // Pruning, if the transfer count is higher and the cost is also higher, it cannot be the shortest path
                if (costToNextNode > distTo[nextNodeID]
                    && nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
                    continue;
                }

                pq.push(State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
            }
        }
        return -1;
    }
};

python 🤖

from heapq import heappop, heappush

class State:
    def __init__(self, id, costFromSrc, nodeNumFromSrc):
        self.id = id
        self.costFromSrc = costFromSrc
        self.nodeNumFromSrc = nodeNumFromSrc
    
    def __lt__(self, other):
        return self.costFromSrc < other.costFromSrc

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        graph = [[] for _ in range(n)]
        for edge in flights:
            from_, to, price = edge
            graph[from_].append([to, price])

        # start the Dijkstra algorithm
        # calculate the shortest path from src to dst with at most k transfers
        K += 1
        return self.dijkstra(graph, src, K, dst)


    # input a source node src, calculate the shortest distance from src to other nodes
    def dijkstra(self, graph, src, k, dst):
        # definition: the shortest path weight from source src to node i is distTo[i]
        distTo = [float('inf')] * len(graph)
        # definition: the minimum weight path from source src to node i must pass through at least nodeNumTo[i] nodes
        nodeNumTo = [float('inf')] * len(graph)
        # base case
        distTo[src] = 0
        nodeNumTo[src] = 0

        # priority queue, nodes with smaller costFromSrc are prioritized
        pq = []
        heappush(pq, State(src, 0, 0))

        while pq:
            curState = heappop(pq)
            curNodeID = curState.id
            costFromSrc = curState.costFromSrc
            curNodeNumFromSrc = curState.nodeNumFromSrc

            if curNodeID == dst:
                # found the shortest path
                return costFromSrc
            if curNodeNumFromSrc == k:
                # transfer count exhausted
                continue

            # add the neighbors of curNode to the queue
            for neighbor in graph[curNodeID]:
                nextNodeID, price = neighbor
                costToNextNode = costFromSrc + price
                # consume 1 transfer count
                nextNodeNumFromSrc = curNodeNumFromSrc + 1

                # update dp table
                if distTo[nextNodeID] > costToNextNode:
                    distTo[nextNodeID] = costToNextNode
                    nodeNumTo[nextNodeID] = nextNodeNumFromSrc
                # pruning, if the transfer count is higher and the cost is also higher, it will not be the shortest path
                if costToNextNode > distTo[nextNodeID] and nextNodeNumFromSrc > nodeNumTo[nextNodeID]:
                    continue

                heappush(pq, State(nextNodeID, costToNextNode, nextNodeNumFromSrc))
        return -1

go 🤖

import (
    "container/heap"
    "math"
)

func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {
    graph := make([][]int, n)
    for i := 0; i < n; i++ {
        graph[i] = []int{}
    }
    for _, edge := range flights {
        from := edge[0]
        to := edge[1]
        price := edge[2]
        graph[from] = append(graph[from], to, price)
    }

    // start the Dijkstra algorithm
    // calculate the shortest path from src to dst with at most k transfers
    K++
    return dijkstra(graph, src, K, dst)
}

type State struct {
    id            int
    costFromSrc   int
    nodeNumFromSrc int
}

// input a starting point src, calculate the shortest distance from src to other nodes
func dijkstra(graph [][]int, src int, k int, dst int) int {
    // definition: the shortest path weight from src to node i is distTo[i]
    distTo := make([]int, len(graph))
    // definition: the minimum weight path from src to node i must pass through at least nodeNumTo[i] nodes
    nodeNumTo := make([]int, len(graph))
    for i := range distTo {
        distTo[i] = math.MaxInt
    }
    for i := range nodeNumTo {
        nodeNumTo[i] = math.MaxInt
    }
    // base case
    distTo[src] = 0
    nodeNumTo[src] = 0

    // priority queue, where states with smaller costFromSrc come first
    pq := &PriorityQueue{}
    heap.Push(pq, &State{src, 0, 0})

    for pq.Len() > 0 {
        curState := heap.Pop(pq).(*State)
        curNodeID := curState.id
        costFromSrc := curState.costFromSrc
        curNodeNumFromSrc := curState.nodeNumFromSrc

        if curNodeID == dst {
            // found the shortest path
            return costFromSrc
        }
        if curNodeNumFromSrc == k {
            // transfer limit exhausted
            continue
        }

        // enqueue the adjacent nodes of curNode
        for i := 0; i < len(graph[curNodeID]); i += 2 {
            nextNodeID := graph[curNodeID][i]
            costToNextNode := costFromSrc + graph[curNodeID][i+1]
            // consume 1 transfer
            nextNodeNumFromSrc := curNodeNumFromSrc + 1

            // update dp table
            if distTo[nextNodeID] > costToNextNode {
                distTo[nextNodeID] = costToNextNode
                nodeNumTo[nextNodeID] = nextNodeNumFromSrc
            }
            // pruning, if the number of transfers is more and the cost is also higher, it will definitely not be the shortest path
            if costToNextNode > distTo[nextNodeID] && nextNodeNumFromSrc > nodeNumTo[nextNodeID] {
                continue
            }

            heap.Push(pq, &State{nextNodeID, costToNextNode, nextNodeNumFromSrc})
        }
    }
    return -1
}

type PriorityQueue []*State

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].costFromSrc < pq[j].costFromSrc
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*State))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

javascript 🤖

var findCheapestPrice = function(n, flights, src, dst, K) {
    let graph = new Array(n).fill(0).map(() => []);
    for (let edge of flights) {
        let from = edge[0];
        let to = edge[1];
        let price = edge[2];
        graph[from].push([to, price]);
    }

    // start the Dijkstra algorithm
    // calculate the shortest path from src to dst with at most k transfers
    K++;
    return dijkstra(graph, src, K, dst);
};

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

// input a starting point src, calculate the shortest distance from src to other nodes
var dijkstra = function(graph, src, k, dst) {
    // define: the shortest path weight from the starting point src to node i is distTo[i]
    let distTo = new Array(graph.length).fill(Infinity);
    // define: the minimum weight path from the starting point src to node i must pass through at least nodeNumTo[i] nodes
    let nodeNumTo = new Array(graph.length).fill(Infinity);
    // base case
    distTo[src] = 0;
    nodeNumTo[src] = 0;

    // priority queue, states with smaller costFromSrc come first
    let pq = new MinPriorityQueue({ priority: (state) => state.costFromSrc });
    pq.enqueue(new State(src, 0, 0));

    while (pq.size() > 0) {
        let curState = pq.dequeue().element;
        let curNodeID = curState.id;
        let costFromSrc = curState.costFromSrc;
        let curNodeNumFromSrc = curState.nodeNumFromSrc;

        if (curNodeID === dst) {
            // found the shortest path
            return costFromSrc;
        }
        if (curNodeNumFromSrc === k) {
            // transfer count exhausted
            continue;
        }

        // enqueue the neighbors of curNode
        for (let neighbor of graph[curNodeID]) {
            let nextNodeID = neighbor[0];
            let costToNextNode = costFromSrc + neighbor[1];
            // consume 1 transfer count
            let nextNodeNumFromSrc = curNodeNumFromSrc + 1;

            // update dp table
            if (distTo[nextNodeID] > costToNextNode) {
                distTo[nextNodeID] = costToNextNode;
                nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
            }
            // pruning, if the transfer count is higher and the cost is also higher, it will definitely not be the shortest path
            if (costToNextNode > distTo[nextNodeID]
                && nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
                continue;
            }

            pq.enqueue(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
        }
    }
    return -1;
};

I won't elaborate on this solution here. You can refer to the previous article Dijkstra Algorithm Template for understanding.

---

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode	力扣
286. Walls and Gates🔒	286. 墙与门🔒

---