preface
Dynamic programming (DP for short) is a very important idea to solve problems in engineering. From the shortest path problem we apply to map software in engineering, to how to collect orders on Taobao in life so as to maximize the use of full reduction coupons to achieve our goal of reasonable wool collection. You can see it a lot of times. Dynamic programming for beginners is really difficult, however, dp, confusing state transfer equation, a lot of people are online feedback is not very studious, actually as before we learn recursion, any learning algorithm has its rules and routines, as long as mastering its rules and the problem solving, plus a lot of exercises to practice, Believe grasp what it is not difficult, this article will use more understandable explanation to help you to master the dynamic programming has a very important idea in the engineering, believes that, after watching the dynamic programming routines must be well-versed in solving problems (article is a bit long, it is recommended that the first collection again, after the play will be the cognition of dynamic programming to rise to a step!)
This article will explain dynamic programming from the following perspectives:
- What is dynamic programming
- Dynamic programming from entry to advanced
- Let’s talk about dynamic programming
What is dynamic programming
Here are my combines the characteristics of dynamic programming presents the definition of the dynamic programming, dynamic programming is a kind of multi-stage decision-making model of the optimal solution is commonly used to get the most value problem, in most cases it can be used in a bottom-up recursive way to draw each sub-problem of the optimal solution (i.e. optimal substructure), then naturally come to depend on the sub-problem of the optimal solution of original problem.
To highlight:
- Multi-stage decision making means that problems can be broken down into sub-problems, sub-problems… In other words, the problem can be divided into multiple sub-problems for solving
- Optimal substructure, in the process of bottom-up recursion, every subproblem we get must be the global optimal solution. Since the subproblems it decomposes are the global optimal solution, then the original problems that depend on their solutions are naturally the global optimal solution.
- How can from bottom to top, from bottom to top to find the optimal solution of each problem, you can be sure there is some connection between sub-problems, namely the iterative recursion formula, also called “the equation of state”, to define the state transition equation, we need to define a good (DP) of the state of each sub-problem, that why to solve it from bottom to top, Because if using such as recursive top-down way of solving, there may be a lot of overlap between sub-problems, a large number of overlapping problem means that a large number of repeated calculation, this time complexity is likely to be exponentially increase (in the following we will see more such repeated calculation result in exponential time complexity). Therefore, the bottom-up solution can eliminate overlapping subproblems.
To sum up briefly, optimal substructure, state transition equation and overlapping subproblem are the three elements of dynamic programming, in which defining the state of the subproblem and writing the state transition equation are the most critical steps to solve the dynamic programming. If the state transition equation is well defined, solving the dynamic programming is basically not a problem.
Now that we know the basic concept and characteristics of dynamic programming, so how to determine whether a topic can use dynamic programming to solve, actually very simple also, when a problem is defined as the most value problem, and the problem can be used in a recursive way, and the recursive process of a large number of repeat subproblems, basic can be concluded that can use dynamic programming to solve the problem, So we get the basic idea of solving dynamic programming as follows (four steps to solve the problem)
- Determine if recursive solutions are available, and proceed to Step 2 if so
- Analyze whether there are a lot of repeating subproblems in the process of recursion
- Use memos to save solutions to subproblems to avoid heavy double-counting (pruning)
- Use a bottom-up approach to recursion, called dynamic programming
May be a lot of people see some of the more dynamic programming is introduced or of some definitions, such as DP state, the equation of state, on the bottom and don’t know, it doesn’t matter, then we will do a few exercises to strengthen the people understanding of these concepts and dynamic programming problem solving four steps, every problem we respectively use recursion, recursive + memo, Let’s do it dynamically, and that will help you further consolidate what we learned about recursion
Dynamic programming from entry to advanced
Introductory question: Fibonacci sequence
Voiceover: The Fibonacci sequence is not strictly a dynamic programming because it does not involve finding a maximum value. This example is intended to illustrate the overlap subproblem and the state transition equation
1. It is obviously possible to determine whether a recursive solution is available. The recursive code is as follows
public static int fibonacci(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Copy the code2. Analyze whether there are a lot of repeat subproblems in the process of recursion
How do you analyze if there’s a repeating subproblem, draw a recursion tree
So you can see that just for f(6), there are two repetitions, f(4) is solved twice, f(3) is solved twice, and the time complexity is exponential, so what about the recursive time complexity, how long does it take to solve each subproblem times the total number of subproblems, how long does it take to solve each subproblemf(n) = f(n-1) + f(n-2)I only did one addition, so how many subproblems do I have, and each problem is divided into two, so it’s a binary tree, and you can see 1 at the first level, 2 at the second level, 4 at the third level1 + 2 + 2^2 +.... 2^n, so the total time is zero
Voiceover: Solve the problem F (6), turn to solve f(5),f(4), start from the original problem, decomposed into sub-problems, sub-problems decomposed into sub-problems,… , until it can no longer be decomposed. This method of solving a subproblem by expanding the original problem is called top-down
Since there are a lot of double computations in the intermediate subproblems above, we can cache the intermediate results (we can use hash table cache) as follows
public static int fibonacci(int n) { if (n = 1) return 1; if (n = 2) return 2; if (map.get(n) ! = null) { return map.get(n); } int result = fibonacci(n - 1) + fibonacci(n - 2); map.put(n, result); return result; }Copy the codeSo let’s see what our recursion tree looks like
You can see that a lot of pruning is done by caching the data in the middle. The same f(4),f(3), and f(2) are all computed once, eliminating a lot of double computation. The size of the problem is changed from a binary tree to a single linked list (n), and the time complexity is changed to
4. Use bottom-up recursion, namely dynamic programming. We noticed the following rule
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 5
....
f(n) = f(n-1) + f(n-2)
Copy the codeSo just solve for f(3) from the bottom up,f(4)… That’s the natural answer
Voice-over: From ultimately no longer decomposable subproblems according to recursive equations(f(n) = f(n-1) + f(n-2))The way you solve a problem is called the bottom up.
f(n) = f(n-1) + f(n-2)It’s the state transition equation
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int result = 0;
int pre = 1;
int next = 2;
for (int i = 3; i < n + 1; i ++) {
result = pre + next;
pre = next;
next = result;
}
return result;
}
Copy the codeSo the time complexity is still
I’m sure you have a better understanding of the bottom-up, DP state, DP transition equation by just doing the Fibonacci example, and those of you who are careful will see why there is no optimal substructure, because as we said before, the Fibonacci sequence is not strictly dynamic programming, I’m just going to use this simple example to help you understand some of the basic concepts. We’re going to see real dynamic programming in future problems
Triage: the sum of the smallest paths of a triangle
As shown in the diagram, the triangle above is made up of a series of numbers, requiring the shortest path from vertex 2 to the bottom. Only two nodes below the current node can be taken at a time. For example, 3 can go to 6 or 5, but not directly to 7.
As shown here, the shortest path from 2 to the bottom is 2+3+5+1 = 11, which is what we want
First of all, we need to use a two-dimensional array to represent the three angular nodes. This can obviously be done with a two-dimensional array. The 2 in the first row is represented by a[0][0], and the elements in the second row 3 and 4 are represented by A [1][0],a[1][1], and so on.
Now that we’ve defined our data structure, let’s see how do we apply our dynamic programming approach to this problem
1. Determine whether recursive solutions are available
So if you do recursion, you’re going to do the sum of all the paths, and then you’re going to minimize the sum of all the paths, so let’s see what you can do with recursion.
For each node that can walk its left or right node, assuming that we define traverse(I, j) as the node a[I][j] to walk next, the pseudo-code of the recursive formula can be obtained as follows
traverse(i, j) = { traverse(i+1, j); Traverse (I +1, j+1) on the left node below nodes I and J; Take a step to the right node below nodes I and j}Copy the codeWhen does it stop? Obviously it stops when you go to the last edge of the triangle. See, for each node, as you go down (to the left or to the right), the problem gets smaller and smaller, and there are critical conditions that stop when you reach the last edge, The subproblems of decomposition also have the same idea of solving the problem (for each node traversal is to the left or right), in line with the conditions of recursion! So we get the recursion code as follows
private static int[][] triangle = { {2, 0, 0, 0}, {3, 4, 0, 0}, {6, 5, 7, 0}, {4, 1, 8, 3} }; public static int traverse(int i, int j) { int totalRow = 4; If (I >= totalrow-1) {return 0; } // traverse(I +1, j) + triangle[I +1][j]; Traverse (I +1, j+1) + triangle[I +1][j+1]; // traverse(I +1, j+1) + triangle[I +1][j+1]; Return math.min (leftSum, rightSum); return math.min (leftSum, rightSum); } public static void main(String[] args) throws Throwable { int sum = traverse(0, 0) + triangle[0][0]; System.out.println("sum = " + sum); }Copy the codeWhat is the time complexity, as you can see from the pseudocode below
traverse(i, j) = { traverse(i+1, j); Traverse (I +1, j+1) on the left node below nodes I and J; Take a step to the right node below nodes I and j}Copy the codeFor each node, either left or right, each problem breaks down into two subproblems, just like the Fibonacci sequence, if you draw a recursion tree it’s also a binary tree, so the time is zero
2. Analyze whether there are a lot of repeat subproblems in the process of recursion
Why time complexity is exponential? Let’s analyze it briefly:
For nodes 3 and 4, if node 3 goes to the right, node 4 goes to the left, and they both get to node 5, and node 5 goes down, it’s going to go through twice, so there’s a repeat subproblem
3. Use memos to save sub-problem solutions to avoid a lot of double calculations (pruning)
Now that it’s there, let’s use memos to cache the intermediate nodes
So our code looks like this
private static int[][] triangle = { {2, 0, 0, 0}, {3, 4, 0, 0}, {6, 5, 7, 0}, {4, 1, 8, 3} }; Private static HashMap<String, Integer> map = new HashMap(); private static HashMap<String, Integer> map = new HashMap(); public static int traverse(int i, int j) { String key = i + "" + j; if (map.get(key) ! = null) { return map.get(key); } int totalRow = 4; If (I >= totalrow-1) {return 0; } // traverse(I +1, j) + triangle[I +1][j]; Traverse (I +1, j+1) + triangle[I +1][j+1]; // traverse(I +1, j+1) + triangle[I +1][j+1]; Int result = math.min (leftSum, rightSum); int result = math.min (leftSum, rightSum); map.put(key, result); return result; }Copy the codeIn this way, the pruning purpose is achieved, and the repetition sub-problem is avoided, and the time complexity is suddenly reduced to
4. Use a bottom-up approach to recursion, namely dynamic programming
How to solve the problem with bottom-up dynamic programming? Let’s look at it this way, to find the shortest path to the bottom of node 2, you take the shortest path to the bottom of node 3 and node 4, and then you take the smallest of those two and you add 2, and you get the shortest path to the bottom of node 3 or node 4, Just take the shortest path to the bottom of their left and right nodes and take the minimum of both and add the value of the node itself (3 or 4).
We know that for the last layer of the triangle, the shortest path to the bottom is itself, so the question becomes how do we get the lowest path to the bottom from the last layer to the last layer of the triangle? So what’s the shortest path to the bottom of the penultimate layer
Similarly, layer 2 for node 3, its shortest path to the lowest level is converted to the minimum value of the shortest path from node 3 to node 7, namely 9, for node 4, its shortest path to the lowest level is converted to the minimum value of the shortest path from node 4 to node 6, and the minimum value of the shortest path from node 10, namely 10.
It’s easy to find the path from 2 to the bottom, just the shortest path from 2 to nodes 9 and 10, which is obviously 11.
So the final 11 is going to be what we’re looking for, and now let’s see how we can define the state and the transition equation for DP. We require the shortest path to the bottom of each node, so the DP state DP[I,j] is defined as the minimum value of the bottom of the node I,j, and the DP state transition equation is defined as follows:
DP[i,j] = min(DP[i+1, j], DP[i+1, j+1]) + triangle[i,j]
Copy the codeThis state transition equation represents the shortest path from the node to the bottom node by taking the minimum of the left and right nodes to the bottom of the shortest path plus the node itself! If we think carefully about whether the above derivation process is derived according to this state transfer equation, I really do not understand the suggestion to read the above derivation process several times, I believe it is not difficult to understand.
DP[I,j] has two variables and needs to loop from bottom to top and left to right to find all I and j, respectively. With the state transition equation, it is relatively easy to find the code, as follows
private static int[][] triangle = { {2, 0, 0, 0}, {3, 4, 0, 0}, {6, 5, 7, 0}, {4, 1, 8, 3} }; public static int traverse() { int ROW = 4; int[] mini = triangle[ROW - 1]; For (int I = ROW - 2; i >= 0; i--) { for (int j = 0; j < triangle[i].length; If (triangle[I][j] == 0) {continue; } mini[j] = triangle[i][j] + Math.min(mini[j], mini[j+1]); } } return mini[0]; } public static void main(String[] args) throws Throwable { int minPathSum = traverse(); System.out.println("sum = " + minPathSum); }Copy the codeThe initial value of mini is the node in the last row, because DP[I,j] of each node in the last row is a fixed value, so you just have to start from the second to last row. Secondly, we know that the shortest path to the bottom of each node is only related to the D[I+1,j], D[I+1,j] of the next layer, so we just need to calculate the DP[I,j] of each layer node and save it in an array, that is why we only need to define the mini one-dimensional array
As shown, the shortest path to the bottom of node 2 is required. It only cares about nodes 9 and 10. Since 9 and 10 are already optimal substructures, just store the maximum value of each layer’s nodes (i.e., a one-dimensional array)!
When bottom-up traversal is completed, the value of mini[0] is DP[0,0], which is the shortest path from node 2 to the bottom. The definition of mini is a little bit convoluted, so you can think about it a few more times, but of course, you can define a two-dimensional array to hold all the DP[I,j], but it takes more space.
Here we’ll talk about optimal substructure, the more we know that in the derivation of nodes in each layer to the bottom of the shortest path depends on it the lower nodes of the shortest path from left to right, from the lower two nodes of the shortest path for dependent on their nodes is optimal substructure, optimal substructure for sub-problem belongs to the global optimal solution, So we don’t have to go for all nodes to the bottom of the path, you just need to rely on its optimal substructure we are looking for the optimal solution is deduced, so the optimal substructure has two meanings, one is that it is the global optimal solution of the subproblem, relies on its upper problem solution is derived based on as long as you have obtained optimal substructure can get global optimal solution, Second, it has the meaning of cache, which avoids the repeated solution of multiple problems that depend on it (eliminating overlapping subproblems).
Conclusion: careful recall our way, we see whether the subject first recursion solutions are available, and in the process of recursive found have overlapping problem, so we use memo to eliminate the overlapping problem of recursion, since we have found this problem can solve with recursive + memo, naturally think of it can use the bottom-up can be solved by dynamic programming. Yes, solving dynamic programming can follow this routine, the most important thing is to find its state transition equation, which requires careful observation in the bottom-up derivation.
Advance: Make small change
Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1. Input: Coins = [1, 2, 5], amount = 11, Output: 3 Explanation: 11 = 5 + 5 + 1 Input: Coins = [2], amount = 3, output: -1
Let’s apply our four steps to dynamic programming
1. Determine whether recursive solutions are available
For Amount, if we choose either coin in Coins, Select any coins for reduced amount until it is no longer possible to select any solution. (Amount <= 0, amount = 0) We can see from the description that the problem can be decomposed into sub-problems, sub-problems and the original problem have the same idea to solve the problem, but also have critical conditions, meet the conditions of recursion, so we can prove that we can use recursion to solve the problem, then let’s see, how to use recursive four steps to solve the problem
1. Define the function of this function. The function of this function is obviously to set an amount and use the defined coins to make up the amount
private static int f(int amount, int[] coins) {
}
Copy the codeAssume that F (amount, coins) is the minimum number of coins required for the amount of coins. After winning the first coin of Coins (i.e. Coins [0]), Then, the minimum number of coins is calculated for the remaining amount of amount-coins [0], that is, f(amount-coins [0], Coins). Thus, the recursive formula after the first coin is selected is as follows
F (amount, coins) = F (amount-coins[0]) + 1Copy the codeWhat if I pick the second and the third, the recursion is as follows
F (amount, coins) = F (amount-coins[1]) + 1 Coins) = F (amount-coins[2]) + 1Copy the codeOur goal is to minimize all of the above f(amount, Coins) solutions, so that we can get our total recursion formula as follows
F (amount, coins) = min{f(amount - coins[I]) + 1)}, where I ranges from 0 to the value of coins. Coins [I] indicates that a coin is selected, and 1 indicates that coins[I] indicates that a coin is selectedCopy the code3. Add the recursive formula of step 2 to the function defined in Step 1
So we have the recursion formula and it’s easy to implement it in code, so let’s look at it a little bit
Public class Solution {private static int exchange(int amount, int[] coins) {if (amount == 0) {return 0; If (amount < 0) {return -1; } int result = Integer.MAX_VALUE; for (int i = 0; i < coins.length; i++) { int subMin = exchange(amount - coins[i], coins); if (subMin == -1) continue; result = Math.min(subMin + 1, result); If (result == integer.max_value) {return -1; } return result; } public static void main(String[] args) throws Throwable { int amount = 11; Int [] COINS =,2,5 {1}; int result = exchange(amount, coins); System.out.println("result = " + result); }}Copy the code(amount = 11) (amount = 11) (amount = 11) (amount = 11) (amount = 11
Earlier we said that Fibonacci’s recursion tree was a binary tree with exponential time complexity, and the change recursion tree was a triadic tree with exponential time complexity!
Second, analyze whether there are a large number of overlapping subproblems in the process of recursion (the second step of dynamic programming) from the recursive tree in the last section, there are overlapping subproblems, 9 and 8 in the last section are repeated, so there are overlapping subproblems!
3. Use memos to save the solutions of sub-problems to avoid a large number of repeated calculations (pruning)
Now that we know there are overlapping subproblems, we can prune with memos to store intermediate results
Private static HashMap<Integer, Integer> map = new HashMap(); private static HashMap<Integer, Integer> map = new HashMap(); Private static int exchangeRecursive(int amount, int[] coins) {if (map.get(amount)! = null) { return map.get(amount); If (amount == 0) {return 0; If (amount < 0) {return -1; } int result = Integer.MAX_VALUE; for (int i = 0; i < coins.length; i++) { int subMin = exchangeRecursive(amount - coins[i], coins); if (subMin == -1) continue; result = Math.min(subMin + 1, result); If (result == integer.max_value) {return -1; } map.put(amount, result); return result; } public static void main(String[] args) throws Throwable { int amount = 11; Int [] COINS =,2,5 {1}; int result = exchangeRecursive(amount, coins); System.out.println("result = " + result); }}Copy the codeFourth, use the bottom-up way to recurse, namely dynamic programming
Previously we derived the following recursive formula
F (amount, coins) = min{f(amount - coins[I]) + 1)}, where I ranges from 0 to the value of coins. Coins [I] indicates that a coin is selected, and 1 indicates that coins[I] indicates that a coin is selectedCopy the codeFrom the above recursive formula, we can obtain the solution idea of DP. We define DP(I) as the minimum value needed to raise enough change for I, and the state transition equation is as follows
DP[I] = min{DP[i-coins [j]] + 1} = min{DP[i-coins [j]]} + 1, where j is the value from 0 to coins, and I represents the value of coins[j].Copy the codeTherefore, we only need to solve DP[1], DP[2],DP[3] successively according to the above state transition equation from bottom to top….. DP[11], and finally DP[11], is our solution
Private static int exchangeDP(int amount, int[] coins) {int[] dp = new int[amount + 1]; For (int I = 0; for (int I = 0; i < amount + 1; i++) { dp[i] = amount + 1; Dp [0] = 0; for (int i = 0; i < amount + 1; i++) { for (int j = 0; j < coins.length; j++) { if (i >= coins[j]) { dp[i] = Math.min(dp[i- coins[j]]+1, dp[i]); } } } if (dp[amount] == amount + 1) { return -1; } return dp[amount]; }Copy the codeVoiceover: This is just the minimum number of coins to make up change, but how can you change it if you want to make up what denominations?
Another way to think about this problem is to use the classic frog jumping step idea. What is the minimum number of steps you can jump from the bottom to the 11th step, one, two, five at a time. The last step must be one or two or five
As shown: the last jump must be 1 or 2 or 5 steps, only required
Write the recursive expression, that is:
F (n) = min{f(n-1), f(n-2), f(n-5)} + 1 (1 represents the last hop)Copy the codeComparing our DP state transition equation, we can find that the two are actually equivalent, but this way of jumping the steps may be easier to understand.
conclusion
This article reinforces the three elements of dynamic programming with a few simple examples: Optimal substructure, the state transition equation, the overlapping problem of understanding, believe that everyone’s understanding of the dynamic programming should be impressed a lot of, how to see whether can use dynamic programming to solve it, look at the topic whether can use recursion is derived, in the process of using a recursive derivation if found to have a lot of overlapping subproblems, there are two ways to optimize, is a kind of recursive + memo, Another kind is to use the dynamic programming, dynamic programming is generally from bottom to top, through state transition equation from the bottom up each sub-problem of the optimal solution (i.e. optimal substructure), optimal substructure is exhaustion of all, it is concluded that the optimal solution obtained after the optimum solution of each sub-problem, namely each optimal solutions is the global optimal solutions of subproblems, So the upper level problem that depends on it naturally leads to a global optimal solution from the state transition equation. Another advantage of the bottom-up solution of dynamic programming is to avoid overlapping subproblems, because there may be many upper-level problems that depend on the subproblems. If the top-down solution is adopted, a large number of overlapping subproblems may be caused, and the time complexity will rise sharply.