# Data structure must be an example to understand dynamic programming (with universal Python code)

### Dynamic programming

​ In the previous section, we learned the basic idea of recursion , We can convert complex problems into minimal problems, so as to simplify complex problems , We can further transform the idea of recursion , When we convert small problems that can be reused （ call ） When , A new idea came into being —— Dynamic programming （Dynamic Programming）.

for instance

​ Take a very common example in life to explain dynamic programming ： In the era of widespread popularity of paper money , When we use paper money to shop, we always involve the problem of change , Suppose we have enough 1、5、10、20、50 A dollar note , Our goal is for a given change value n, So that we can use as little money as possible （ Few sheets ）.

​ According to the experience of spending money , See this problem , We will certainly think of such a strategy ：1、 Use as many banknotes with the largest denomination as possible ,2、 Try to use the second largest denomination … And so on . According to such strategies , We can use this method to achieve the purpose of using the least money , This method is also called Greedy algorithm . such as ：63 = 50+10+1*3.

​ Now take an unconventional route （ After all, programming scenarios are different from life ）, The denomination of a country's paper money is 1、5、11 Three , Now the amount of change we want is 15 element , We will get the following results ：

• Greedy algorithm ：15 = 11+1*4（5 Zhang ）

• right key ：15 = 5*3（3 Zhang ）

​ In this case, we will find , The greedy algorithm we used before made a mistake , The greedy algorithm allows us to consider only the interests of the immediate situation , Not considering the whole , Naturally there will be mistakes .

• Choose... First 11 What will happen to Yuan ？
• Number of sheets required = f(4) +1 = (1 element )*4 + 1 = 5 Zhang
• above 1 It means to use one 11 Yuan note , The same below .
• Choose... First 5 What will happen to Yuan ？
• Number of sheets required = f(10) + 1 = (5 element )*2 + 1 = 3 Zhang
• Choose... First 1 What will happen to Yuan ？
• Number of sheets required = f(14) + 1 = (11 element )*1 + (1 element )*3 + 1 = 5 Zhang

​ According to the above process, try to select all types of paper money first , You can find the right decision , Therefore, the core of the above method can be obtained ：

​ We're about the change value n And the minimum number of notes f(n) Have a conclusion ：f(n) Only with f(n-11),f(n-5),f(n-1) relevant , So we can get our calculation method is ：

f ( n ) = m i n { f ( n − 1 ) , f ( n − 5 ) , f ( n − 11 ) } + 1 f(n)=min\left \{f(n-1),f(n-5),f(n-11)\right \}+1

​ With this about f(n) Formula , Can we get anything f(n) It's worth it ？ Similarly, we can call recursively f(n) The expression of , This is the idea of realizing dynamic programming .（ Later, it will be implemented through code ）

Dynamic programming is a three-step process

• Establish the state transition equation

This step is the core of our dynamic planning , Its core lies in ： When we already know f ( 1 ) − f ( n − 1 ) f(1)-f(n-1) Value , Then we need to find a way to use them to find f ( n ) f(n) , Get a state transition equation （ The formula ）.

• Cache and reuse past results

This step is mainly to speed up our calculation process , Simply put, if now f ( 100 ) f(100) Unknown , But we just got f ( 99 ) f(99) , If not f ( 99 ) f(99) cached , Then let's ask f ( 100 ) f(100) Ask for the sum of all the previous items again , This shows the importance of cache reuse .

• Count from small to large in order

When looking for and using the state transition equation , We basically passed the first few ： f ( 0 ) , f ( 1 ) , f ( 2 ) , f ( 3 ) f(0),f(1),f(2),f(3) To find the transition state , So usually we can only calculate from small to large , Otherwise, you may disrupt your thinking .

Recursive implementation code （ Example ）

​ Using the simplest recursive method, we can get the solution of the above problem , But in recursion, we almost list all the cases , Then look for the scheme with the least number of notes , Let's take a look at the implementation of recursion ：

# dp Dynamic programming

'''  Parameter description ： coinValueList: Existing types of coins （list） change: The amount of money that needs to be scraped up  knownResults: whole 0 A list of , Used to store the previously calculated results  '''

def recDC(coinValueList, change, knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
elif knownResults[change] > 0:
return knownResults[change]
else:
#  Traverse and select each coin
for i in [c for c in coinValueList if c <= change]:
#  Flip the selected coin , Recursively process the rest of the money
numCoins = 1 + recDC(coinValueList, change - i, knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
return minCoins

recDC([1, 5, 11], 63, [0] * 64)

#  Output
# 9


Dynamic programming （ Example ）

​ Using dynamic programming, we can avoid the tedious enumeration process like recursion , According to the dynamic programming mentioned above, three steps , We from 1 The change of Yuan starts , And then there was 2 element 、3 element , This is actually what we are calculating f(0)、f(1)、f(2) The process of , This calculation goes on , When our change is n Yuan time , We can not only calculate f(n), You can also get f(n-1)、f(n-2)…f(0) These results , At this time, if our change is more than n Small , Then we can get the results directly . The specific code implementation of dynamic programming is as follows ：

# dp Dynamic programming

def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
for cents in range(change + 1):
coinCount = cents
newCoin = 1
for j in [c for c in coinValueList if c <= cents]:
#  Dynamic transfer to find the minimum
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
newCoin = j
minCoins[cents] = coinCount
coinsUsed[cents] = newCoin
return minCoins[change]

def printCoins(coinValueList, change, minCoins, coinsUsed):
minc = dpMakeChange(coinValueList, change, minCoins, coinsUsed)
print(" Minimum number of notes ：", minc)
coin = change
print(" Required note denomination ：")
while coin > 0:
thisCoin = coinsUsed[coin]
print(thisCoin)
coin = coin - thisCoin

c1 = [1, 5, 11]
coinsUsed = [0] * 64
coinCount = [0] * 64
printCoins(c1, 17, coinCount, coinsUsed)

#  Output
'''  Minimum number of notes ： 3  Required note denomination ： 1 5 11 1 '''


https://cdmana.com/2021/10/20211002150018476I.html

Scroll to Top