After reading this article, you can try to solve the following problems:
The cheapest flight within the 787.K stop (Medium)
Joking aside, graduation season, to the past may be some joy and sadness, to the future may be some confusion and yearning, but these are all fleeting clouds, sooner or later will be diluted and forgotten by time.
At the end of this wonderful time, it is really appropriate to have a graduation trip, presumptuous, to draw a perfect full stop for youth.
So, this article teaches you a dynamic programming algorithm to save money in graduation travel, save the pursuit of poetry and distant capital.
Let’s say you’re going to travel from your university city to multiple cities, all the way to the company. How can you arrange your travel to minimize the cost of airfare?
Let’s take a look at question 787, “Cheapest flight within K station”. Let me describe the question:
Now we have n cities, 0,1… For example, the triplet [0,1,100] indicates that the ticket price from city 0 to city 1 is 100 yuan.
You will be given a number of parameters:
The positive integer N represents the number of cities, the array FLIGHTS holds several triples representing flight routes and prices between cities, the city number SRC represents your city, the city number DST represents your destination city, and the integer K represents the maximum number of transit stations you have passed through.
The function signature is as follows:
int findCheapestPrice(int n, int[][] flights, int src, int dst, int K);
Copy the codeAsk your algorithm to calculate the minimum cost required to get from SRC to DST within K relays, and return -1 if it cannot be reached.
Take the example given by the question:
N = 3, flights = [,1,100 [0],,2,100 [1], [0,2,500]], the SRC = 0, DST = 2 and K = 0
The route is shown in the picture below. The directional edge represents the direction of the route, and the numbers on the edge represent the ticket price of the route:
The starting point is 0, the arrival point is 2, and the maximum allowed transit times K is 1, so the minimum cost is the two red edges in the figure. Starting from 0, the algorithm reaches the target city 2 through transit city 1, so the return value of the algorithm should be 200.
Note that the upper limit of the number of transitions, K, is tricky. If the above problem changes K to 0, that is, no transitions are allowed, then our algorithm will only return 500, that is, fly directly from 0 to 2.
Obviously, this is a shortest path problem in a weighted directed graph.
In other words, you are given a weighted directed graph and asked to find the path from SRC to DST with the least weight, ** and ** the path must have at most K + 1 edges (K nodes equals K + 1 edges).
Let’s look at the shortest path correlation algorithm.
BFS algorithm idea
As we have said in the detailed explanation of the core routine of dynamic programming, many problems of optimal value can be solved by dynamic programming.
The weighted shortest path problem, plus a K constraint, is also a maximization problem, dynamic programming all down.
Let’s ignore the K constraint, and let’s just look at the weighted shortest path problem, how can it be a dynamic programming problem?
For example, now I want to calculate the shortest path from SRC to DST:
What is the minimum weight? I don’t know.
But I can break it down:
S1 and S2 are adjacent nodes that point to DST, and the weights between them I know are w1 and w2.
As long as I know the shortest path from SRC to S1 and s2, I know the shortest path from SRC to DST.
minPath(src, dst) = min(
minPath(src, s1) + w1,
minPath(src, s2) + w2
)
Copy the codeIt’s just a recursive relationship. It’s as simple as that.
But remember, they also have a limit of K + 1 edges on our shortest paths.
So let’s define a dp function like this:
int dp(int s, int k);
Copy the codeThe function is defined as follows:
Starting from the starting point SRC, the minimum path weight to reach node S within k steps (a step is an edge) is dp(s, k).
So, the base case of the dp function is obvious:
Int dp(int s, int k) {if (s == SRC) {return 0; } // If (k == 0) {return -1; } / /... }Copy the codeThe minimum cost can be expressed as dp(DST, K+1) :
Int findCheapestPrice(int n, int[][] flights, int SRC, int DST, int K) { / /... return dp(dst, K);Copy the codeIf I add a K edge constraint, how do I write the state transition equation? It’s 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 it down:
S1, s2 is a neighboring node that points to DST. If I can get from SRC to S1 and S2 in k-1 steps, I can get from SRC to DST in K steps.
That is, the following relationship:
dp(dst, k) = min(
dp(s1, k - 1) + w1,
dp(s2, k - 1) + w2
)
Copy the codeSo this is the new state transition equation, and if you can read this formula, you can already solve this problem.
Code implementation
How do I know that s1 and s2 are adjacent nodes to DST and that their weights are w1 and w2?
I want to give a node, and I want to know who points to that node, and I want to know the weights between them, right.
Technically, use a data structure to record the “entry” of each node 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) {public int findCheapestPrice(int n, int[] flights, int SRC, int DST, int 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); }Copy the codeWith indeGREE stored in, we can implement the dp function in detail:
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)) {for (int[] v: indegree.get(s)) {int from = v[0]; if (indegree.containsKey(s)) {int from = v[0]; int price = v[1]; Int subProblem = dp(from, k-1); int subProblem = dp(from, k-1); // Skip if (subProblem! = -1) { res = Math.min(res, subProblem + price); Return res == integer.max_value? -1 : res; }Copy the codeGiven the preamble, the logic of this solution should be clear. Of course, for dynamic programming problems, overlapping subproblems must be eliminated.
Why are there overlapping subproblems? Very simply, if a node points to two other nodes at the same time, then the two nodes have the same entry node, resulting in repeated recursive calculations.
How do I eliminate the overlap subproblem? Find the “state” of the problem.
What’s the state? What changes during problem decomposition (state transition) is the state.
Who is changing? It is obviously the parameters s and k of the dp function, and the target point S and the step constraint K change with each recursive call.
Therefore, we can use a memo array or hash table as a memo to reduce the double computation.
Let’s use a two-dimensional array for memos. Note that K starts at 1, so the initial size of the memos should be incremented by one:
int src, dst; HashMap<Integer, List<int[]>> indegree; // memo 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); } // other unchanged //... return dp(dst, K); } base case if (s == SRC) {return 0; base case if (s == SRC) {return 0; } if (k == 0) { return -1; } // If (memo[s][k]! = -888) { return memo[s][k]; } // State transition does not change //... Memo [s][k] = res == integer.max_value? -1 : res; return memo[s][k]; }Copy the codeWhy is the initial value of memo -888? Above dynamic programming core routine, in fact, there is really no difficult.
View more quality algorithm articles click here, hand with your brush force buckle, committed to the algorithm to speak clearly! My algorithm tutorial has received 90K star, welcome to like!