©2020-2024 ioDraw All rights reserved
什么是递归
递归是一种解决问题的方法，将问题分解为更小的子问题，直到得到一个足够小的问题可以被很简单的解决。通常递归涉及函数调用自身
。递归允许我们编写优雅的解决方案，解决可能很难编程的问题。
递归的三定律
* 1. 递归算法必须具有基本情况。
* 2. 递归算法必须改变其状态并向基本情况靠近。
* 3. 递归算法必须以递归方式调用自身。
递归实例
def listsum(numList): if len(numList) == 1: return numList.pop() #基本情况 else:
#改变状况向基本情况靠近 return numList.pop() + listsum(numList) #调用自身
print(listsum([1,3,5,7,9]))
动态规划
动态规划的实质是分治思想和解决冗余，因此动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题
，已解决最优化问题的算法策略。
最少硬币找零
假设你是一个自动售货机制造商的程序员。 你的公司希望通过给每个交易最少硬币来简化工作。假设客户放入 1 美元的钞票并购买 37 美
分的商品。你可以用来找零的最小数量的硬币是多少？答案是六个硬币：两个 25 美分，一个 10美分 和
三个一美分。我们如何得到六个硬币的答案？我们从最大的硬币（25 美分）开 始，并尽可能多，然后我们去找下一个小点的硬币，并尽可能多的使用它们。这第一种方法
被称为贪婪方法，因为我们试图尽快解决尽可能大的问题。 def recDC(coinValueList,change,knownResults):
minCoins = change if change in coinValueList: #首先判断当前金额是否可以正好找零
knownResults[change] = 1 return 1 elif knownResults[change] > 0:
#其次查看已经计算过的列表，是否可以找到结果 return knownResults[change] else: for i in [c for c in
coinValueList if c <= change]: #选出面值小于找零金额的钱用于找零 numCoins = 1 +
recDC(coinValueList, change-i,knownResults) if numCoins < minCoins: minCoins =
numCoins knownResults[change] = minCoins #更新储存计算结果的列表 return minCoins
knownResults = [0]*64 #0是因为没有用过 print(recDC([1,5,10,25],63,knownResults))
print(knownResults) def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
for cents in range(change+1): newCoin = 1 #初始情况全部使用1面额硬币找零 coinCount = cents
#初始情况金额即使数量 for j in [c for c in coinValueList if c <= cents]:
#从硬币中筛选出面额小于找零金额的硬币进行找零 if minCoins[cents-j] + 1 < coinCount: #先用一个硬币，找零数额所以 +
1，之后查看剩余金额所需硬币数量。这个是前面计算好的，动态规划的。 coinCount = minCoins[cents-j]+1
#如果总数量小于当前计划数量，更新动态规划结果 newCoin = j #更新后的结果用于下次计算 minCoins[cents] = coinCount
#更新 coinsUsed[cents] = newCoin #更新 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) #硬币数量 coinCount = [0]*(amnt+1)
#硬币面额 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()