Dynamic programming algorithm is one of the most important and commonly used algorithms in computer science. It can solve many complex problems by clever use. In addition, it frequently appears in interviews of Internet companies, so it is very necessary to master it.
But the algorithm for beginners, to thoroughly understand it is not easy, this series of tutorials will lead you to learn the algorithm, through the classic case introduction and problem analysis, trying to induce a set of unified methods to solve dynamic programming problems. This series focuses on the ideas and methods of analyzing problems, rather than directly telling you the answer, giving you different ideas of analyzing problems.
First let’s take a look at a very classic “coin” problem:
The face value is 1 yuan, 3 yuan, 5 yuan coins several, how to use the least coins to make up 11 yuan?
Answer:
Step 1: Write the results in functional terms.
Let’s say that f of x is equal to y, which means that we have x dollars, and the minimum number of coins is y. Examples are as follows:
- If the minimum number of coins for a dollar is 1, f(1) = 1
- If the minimum number of coins for 11 dollars is 3, this is f(11) = 3
Step 2: Analyze the recursion.
To raise 11 yuan, we need to choose several times. For example, if we choose 1 yuan for the first time, we need to raise 11-1 = 10 yuan.
The second time choose 3 yuan, then need to raise 10-3 = 7 yuan; .
If we chose a 1 dollar coin, then f of 11 is equal to 1 plus f of 11 minus 1, which means we got 11 dollars and we chose a 1 dollar coin, so we’re left with the number of coins f of 10 that need to get 11 minus 1 is equal to 10 dollars.
Similarly, if you choose 3 elements then f(11) = 1 + f(11-3), and if you choose 5 elements then F (11) = 1 + f(11-5).
They’re asking us to make 11 dollars using the least amount of coins, so
f(11) = min{ 1+f(10) , 1+f(8), 1+f(6)}
Note: here you should fully understand the meaning of f(x) function, f(x) is the minimum number of coins needed to raise X yuan.
By analyzing f(11), we know that if we want to solve f(11), we have to solve f(10), f(8), and f(6).
f(10) = min{1+f(10-1), 1+f(10-3), 1+f(10-5)}
f(8) = min{1+f(8-1), 1+f(8-3), 1+f(8-5)}
F (6) = min{1+f(6-1), 1+f(6-3), 1+f(6-5)}…
Therefore, in order to solve f(11),f(10), F (8),f(6) must be solved first, and to solve F (10),f(9), F (7), f(5) must be solved first. Similarly, when we calculate the value of the previous function, we can naturally obtain the result of the later function very conveniently. That’s the beauty of dynamic programming algorithms.
After careful analysis of F (11), we can easily conclude that the general situation is:
f(i) = min{ 1+f(i-1), 1+f(i-3), 1+f(i-5)}
There are three options for collecting I dollars: one is 1 yuan, one is 3 yuan, and one is 5 yuan, and then choose the smallest of the three options. So that’s the recursion that we got for the general case. This recursive formula is particularly important for solving dynamic programming problems.
That’s how we analyze recursion, if you understand.
Step 3: Algorithm implementation
After we understand the solution of the problem, we can choose any familiar programming language to achieve, such as C, Java and so on.
If you do not understand the idea of algorithms, do not understand the ideas and methods of problem analysis, even if you are proficient in any programming language, because you have no way to start, this is always emphasized the importance of algorithm ideas, problem analysis ideas and methods.
Just because you know how to solve a problem doesn’t mean you can program it. As for the programming implementation of this problem, we will open up a new article to introduce and analyze some problems that need to be paid attention to in the programming implementation. If you are interested, please pay attention to the public number at the end of the article.
Conclusion:
For any dynamic programming topic, we can basically follow the above three steps to analyze, the following article will continue to explain the analysis ideas in detail.
