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 I choose 3, then F