Dynamic programming was proposed by American mathematician Behrman in the 1950s to study optimal control problems. After the value of this method in applied mathematics was recognized by everyone, dynamic programming method became a general algorithm design technology used to solve multi-stage decision optimization problems in the field of computer science.
So, class, the dynamic programming problem that you find particularly difficult was thought up in 1950, 70 years ago. In addition, some students should not ask whether computers can change the world, ok? It’s hard to change the world by writing CRUD, but coming up with ideas like dynamic programming, Paxos, Raft, etc., or being able to take what’s already in math and turn it into a computer is great!!
Dynamic programming method is to decompose the problem to be solved into several sub-problems, but the sub-problems are often not independent of each other. In the dynamic programming method, each subproblem is solved only once and its solution is saved in a table. When the subproblem needs to be solved again, the solution of the subproblem is simply obtained by looking up the table, thus avoiding a lot of repeated calculation.
An overview of the
Optimization problem
There are n inputs, and its solution consists of a subset of those n inputs, and that subset must satisfy certain pregiven conditions, called constraints, and solutions that satisfy constraints are called viable solutions to the problem. There may be more than one feasible solution satisfying the constraint conditions. In order to measure the merits of these feasible solutions, certain standards are given in advance, which are usually given in the form of functions, called objective functions. The feasible solution that causes the objective function to obtain the extreme value is called optimal solution, and this kind of problem is called optimization problem.
Principle of optimality
For an optimization problem with n inputs, the solution process is usually divided into several stages, and the decision at each stage only depends on the state at the previous stage, and the action taken by the decision makes the state transfer, which becomes the basis for the decision at the next stage.
S is the state and P is the policy. If a state can make multiple decisions and each decision can generate a new state, the decision-making process of dynamic programming is as follows:
The multi-decision process satisfies the principle of optimality: no matter what the initial state and initial decision of the decision process are, the remaining decisions must constitute an optimal decision sequence relative to the current state generated by the initial decision
Therefore, it is a process of continuously calculating states and strategies from front to back, and then backtracking from back to front to find the optimal link.
The design idea of dynamic programming method
The dynamic programming method makes use of the optimality principle of the problem and constructs the optimal solution of the whole problem step by step from the optimal solution of the sub-problem in bottom-up manner. The application of dynamic programming design algorithm is generally divided into three stages:
1) Segmentation: Decompose the original problem into several overlapping sub-problems
2) Analysis: analyze whether the problem meets the optimality principle and find out the recursion of dynamic programming function
3) Solution: use recursive bottom-up calculation to realize the dynamic planning process
Dynamic programming method in graph problem
The TSP problem
The TSP problem refers to that the traveler has to travel n cities, and is required to experience each city only once, and then return to the starting city, and is required to travel the shortest distance.
Take this question as an example to explain how to solve the problem
-
Prove by contradiction that this problem conforms to the principle of optimality
Suppose s, S1, S2,… , sp, S are the shortest simple loop, then the shortest path from S1 to S is still S1, S2… , SP, S, if s1, R1, R2…… , rq and S are shorter, then S, S1, R1, R2…… , Rq, S are the shortest simple loop from S to S, which leads to contradiction
-
Draw the decision tree and find the dynamic programming recursion
Let’s say I have four nodes: 0, 1, 2, 3
The recursion has to correspond to the problem, so that’s a trick point.
- Solve problems by hand, find patterns – usually from the bottom up, and record the results
- Find the recursion formula
- Discover patterns and determine which results to record. How do I remember it, whether it’s a table or an array, how do I find these values
- 64. Minimum path and medium code to solve this problem, follow the pattern does get the correct solution, but time out. Because of the rules, I used the bottom-up method, doubling the time and space. It’s actually better to go with the top-down approach. So don’t be superstitious about templates, but be flexible. Of course, from another aspect also shows that this model is feasible, but when you look at the problem, you need to think more fully.
- Sword refers to Offer 47. Maximum value of a gift – medium code for this variant of question 1
The shortest path problem of multisegment graph
Let G=(V,E) be a weighted directed connected graph. If the set of vertices V is divided into k disjoint subsets Vi(2<=k<=n,1< = I <=k), such that any edge (u, V) in E must belong to Vi, and V must belong to Vi+ M (1<= I <k,1< I +m<=k), then G is called a multi-segment graph. Say s belongs to V1 as the source point and T belongs to Vk as the end point. The shortest path problem of multisegment graph is to find the least cost path from source point to end point.
The only difference is in the recursive formula: Cost [n] is used as a table to store the solutions of the subproblem, cost[I] represents the shortest path from vertex I to end n-1,
Cost [I]=min{cij+cost[j]}, ij is the two points connected
You can see that the intermediate result values are recorded using arrays, whereas the TSP uses a two-dimensional table.
The reason for this problem is that the process from the specified point to the end point of the multi-segment graph is determined. For example, vertex 1 must go through three times to reach the end point, which will not be repeated, resulting in only one minimum value. Therefore, one-dimensional array is used for storage. But TSP vertex 1, which can be either the first or the last vertex from the starting point, has a minimum value for each phase, so it’s stored in a two-dimensional array.
- Interview question 08.01. Three-step Questions – Simple code With easy questions
- 70. Take the stairs – The simple code solution is the same as the first question
- 120. Triangle minimum path and – medium code
Dynamic programming method for combinatorial problems
0/1 knapsack problem
Given n items and a backpack, the weight of item I is WI, its value is VI, and the backpack’s capacity is C. The backpack problem is how to choose the items to be loaded into the backpack so that the total value of the items to be loaded into the backpack is maximum?
Recursive formula: Let V(I,j) represent the maximum value of items that can be loaded into the backpack with capacity j(1<=j<=C) in the first I (1<= I <=n) items, then the following dynamic programming function can be obtained
-
V(i,0)=V(0,j)=0
V(i-1,j), j < wi
-
V(i,j)=
max{ V(i-1,j), V(i-1,j-wi)+vi }, j >= wi
The first formula of V(I,j) indicates that: if the weight of the ith item is greater than the capacity of the backpack, the maximum value of the I item before loading is the same as the maximum value of the I-1 item before loading, that is, the item cannot be loaded into the backpack
The second formula shows that: if the weight of the ith item is less than the capacity of the backpack, there will be the following two situations: (1) If the ith item is put into the backpack, the value of the item in the backpack is equal to the value of the former I-1 item into the backpack with the capacity of J-WI plus the value of the ith item vi; (2) If the i-th item is not loaded into the backpack, the value of the items in the backpack is equal to the value obtained by putting the previous I-1 item into the backpack of capacity J. I’m obviously going to take the larger of them.
Analysis:
The 0/1 knapsack problem is a little more complicated than the graph problem because of the added capacity limitation. However, the dynamic programming function shown is excellent. V(I,j) represents the maximum value of the previous I items under j capacity, which perfectly states the desired result and clearly states the specific implementation of the code.
As the algorithm runs, start at zero and keep increasing the capacity to see what is the maximum number of items you can put in. The calculation goes from front to back. In fact, this problem also refers to a core of dynamic programming – recording sub-results.
If there are 5 goods with weight {2,2,6,5,4}, value {6,3,5,4,6} and backpack capacity of 10, then the two-dimensional table in the calculation process is:
The method to determine which item to put in the backpack is as follows: For the column with capacity 10, if the value of the next column is larger than that of the previous column, it indicates that the item is to be put in the backpack.
-
Sword refers to Offer 63. Maximum profit on stock – medium code
-
121. Best Time to Buy or Sell Stocks – Simple code
These two questions also explain why I said before that le Buckle may be weak in professionalism. The logic is completely consistent, but the difficulty level is different.
Backpack problem I did not find a suitable example on the buckle, and backpack problem is relatively complex, the difficulty should be on the difficulty. The two problems above are somewhat similar, and again prove that the core of dynamic programming is recording sub-results. And we’re going to find some hard ones to do.
Longest common subsequence problem
For a given sequence X=(x1, X,2… ,xm) and sequence Z=(z1,z2… ,zk), Z is a subsequence of X if and only if there exists a strictly increasing subscript sequence (i1,i2… ,ik), so that for all j=1,2… ,k, zj=xij(1<=ij<=m). If the sequence X=(a,b,c,b,d,a,b), the sequence (b,c,d,b) is a subsequence of X with length 4, the corresponding increasing subsequence is (2,3,5,7).
Given two sequences X and Y, Z is said to be a common subsequence of sequences X and Y when the other sequence Z is both a subsequence of X and a subsequence of Y. The longest common subsequence problem is to find the longest common subsequence in the common subsequence of sequences X and Y.
Z (I,j) represents the largest substring of the first I characters of X and the first j characters of Y, where j is row and I is col
Z (I -1,j-1)+1 xi==yj, top left
z(i,j) =
max{z(i-1,j),z(i,j-1)} xi! =yj
This is a recursive formula that I came up with on my own, so it gives me a little bit more insight into dynamic programming.
- Longest common subsequence – medium code
Find the dynamic programming method in the problem
Optimal lookup binary tree
Set {r1, r2,… Rn} is the set of n records, whose search probabilities are {p1,p2… ,pn}, the optimal binary search tree is the binary search tree with the least average comparison times among the binary search tree composed of n records, that is, sum(PI * CI) is the smallest, where PI is the search probability of record RI, ci is the comparison times of search RI in the binary search tree.
Let T(I,j) be given by the record {ri… ,rj}(1<= I <=j<=n), C(I,j) is the average comparison times of this binary search tree, then the function is dynamically planned
The main difficulty of this problem is deriving the dynamic programming function. Once deriving the function, the rest of the process is consistent with the above problem.
There is no algorithm problem on the buckle, so I will not practice first. In fact, after deriving the dynamic programming function, the whole calculation logic has been relatively clear.
Approximate string matching problem
Set the sample P = p1p2… PM, text T= t1T2…… Tn, for a non-negative integer K, the K- approximate match of sample P in text T is the match where P contains at most K differences in T. The difference here refers to one of three cases:
1) Modification: P and T correspond to different characters
2) Delete: T contains a character that does not appear in P
3) Insert: T does not contain a character that appears in P
Define D(I,j)(0<= I <=m,0<=j<=n) to represent sample prefix substring P1…… PI and the text prefix substring T1…… The minimum difference between tj, and the recursive formula is:
I will not write this kind of repetitive topic, and there is really no suitable topic on the buckle.
conclusion
I’m finally done with dynamic programming. When I was in college, I was afraid of the topic of dynamic programming, because I did not fully understand it. But fortunately, after this re-study, I gave myself the positioning is: finally get started.
After all, dynamic programming follows the same pattern:
- Proof by contradiction satisfies the optimality principle
- Derive the dynamic programming function – this is the most important point
- Recording intermediate process
Help something
- The core of the core is documenting the intermediate process
- Before deriving the dynamic programming function, ensure that the function satisfies the solution of the problem
- You can draw diagrams to help you derive dynamic programming functions
As for the exercises, I suggest that the topic in this article, we all do, and think of their own dynamic programming function. Hopefully everyone can learn this algorithm.
The last
If you like my article, you can follow my public account (Programmer Malatang)
My personal blog is shidawuhen.github. IO /
Review of previous articles:
algorithm
- Algorithmic learning plan
- A brute force method
- Divide and conquer method
- Reduction treatment
- Dynamic programming method
technology
- Service framework and registry for microservices
- Beego framework use
- Discussion on Micro-service
- TCP Performance Optimization
- Current limiting implementation 1
- Redis implements distributed locking
- Golang source BUG tracking
- The implementation principle of atomicity, consistency and persistence of transactions
- CDN request process details
- The story of how blogging services were crushed
- Common Cache tips
- How to effectively connect with third-party payment
- Gin framework concise version
- InnoDB locks and transactions
Reading notes
- Agile revolution
- How to exercise your memory
- Simple Logic – After reading
- Hot Wind – After reading
- Analects of Confucius – After reading
thinking
- Some thoughts on project management
- Some thoughts on product manager
- Thinking about programmer career development
- Thinking about code review
- Markdown editor recommends – Typora