什么是递归

递归是一种解决问题的方法,将问题分解为更小的子问题,直到得到一个足够小的问题可以被很简单的解决。通常递归涉及函数调用自身
。递归允许我们编写优雅的解决方案,解决可能很难编程的问题。

递归的三定律

* 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()
 

技术
©2020 ioDraw All rights reserved
PHP 先返回结果到前端,PHP代码继续执行后续的任务程序员升职记第28关三排序代码中介效应、调节效应与交互作用咋回事?详解PHP中的die、exit、returnpython中的gc回收机制k8s删除podVue2.0+jsonserver+axios模拟本地请求接口数据逆向工程核心原理笔记(一)——Hello World-1spark.sql.shuffle.partitions 和 spark.default.parallelism 的区别Keras输出模型的各层的结果