What is recursion
Recursion is a way to solve problems , Decompose the problem into smaller subproblems , Until you get a small enough problem that can be easily solved . Recursion usually involves the function call itself
. Recursion allows us to write elegant solutions , Solve problems that can be difficult to program .
Three laws of recursion
* 1. Recursive algorithms must have a basic case .
* 2. Recursive algorithm must change its state and approach the basic situation .
* 3. Recursive algorithms must call themselves recursively .
Recurrence Examples
def listsum(numList): if len(numList) == 1: return numList.pop() # Basic information else:
# Change the situation and get closer to the basic situation return numList.pop() + listsum(numList) # Call itself
print(listsum([1,3,5,7,9]))
dynamic programming
The essence of dynamic programming is to divide and rule and solve redundancy , Therefore, dynamic programming is a kind of decomposition of problem instances into smaller ones , Similar subproblems , A subproblem with the solution of storage subproblem to avoid repeated calculation
, Algorithmic strategies for solving optimization problems .
Minimum change
Suppose you are a programmer for a vending machine manufacturer . Your company wants to simplify work by giving a minimum of coins per transaction . Suppose the customer puts in 1 Dollar bills and purchases 37 beautiful
Divided goods . What is the minimum number of coins you can change ? The answer is six coins ： Two 25 cent , One 10 cent and
One cent for three . How do we get the answer for six coins ? We start with the largest coin （25 cent ） open beginning , And as much as possible , Then we go to the next smaller coin , And use them as much as possible . This first method
It's called the greedy method , Because we're trying to solve the biggest problem as soon as possible . def recDC(coinValueList,change,knownResults):
minCoins = change if change in coinValueList: # First, judge whether the current amount can be changed exactly
knownResults[change] = 1 return 1 elif knownResults[change] > 0:
# Second, look at the calculated list , Can the results be found return knownResults[change] else: for i in [c for c in
coinValueList if c <= change]: # Choose the money whose face value is less than the change amount and use it for change numCoins = 1 +
recDC(coinValueList, change-i,knownResults) if numCoins < minCoins: minCoins =
numCoins knownResults[change] = minCoins # Update the list of stored calculation results return minCoins
knownResults = [0]*64 #0 Because I didn't use it print(recDC([1,5,10,25],63,knownResults))
print(knownResults) def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
for cents in range(change+1): newCoin = 1 # The initial conditions are all used 1 Change in denomination coinCount = cents
# Initial situation amount even quantity for j in [c for c in coinValueList if c <= cents]:
# The coins with denomination less than the change amount are selected from the coins for change if minCoins[cents-j] + 1 < coinCount: # Use a coin first , Change, so +
1, Then check the number of coins required for the remaining amount . This is the previous calculation , Dynamic programming . coinCount = minCoins[cents-j]+1
# If the total quantity is less than the current planned quantity , Update dynamic planning results newCoin = j # The updated results are used for the next calculation minCoins[cents] = coinCount
# to update coinsUsed[cents] = newCoin # to update return minCoins[change] def
printCoins(coinsUsed,change): coin = change while coin > 0: thisCoin =
coinsUsed[coin] print(thisCoin) coin = coin - thisCoin def main(): amnt = 63
clist = [1,5,10,25] coinsUsed = [0]*(amnt+1) # Number of coins coinCount = [0]*(amnt+1)
# Denomination of coins print("Making change for",amnt,"requires")
print(dpMakeChange(clist,amnt,coinCount,coinsUsed),"coins") print("They are:")
printCoins(coinsUsed,amnt) print("The used list is as follows:")
print(coinsUsed) print(coinCount) main()
Technology