编程知识 cdmana.com

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 .

​ Think about this from multiple perspectives ( use f(n) Medium n Represents the amount ):

  • 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 f(n)=min{ f(n1),f(n5),f(n11)}+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) f(1)f(n1) Value , Then we need to find a way to use them to find f ( n ) 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) f(100) Unknown , But we just got f ( 99 ) f(99) f(99), If not f ( 99 ) f(99) f(99) cached , Then let's ask f ( 100 ) 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) 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 '''

版权声明
本文为[The second brother is not like a programmer]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211002150018476I.html

Scroll to Top