递归算法也总结出 三定律
1,递归算法必须有一个基本结束条件（最小规模问题的直接解决)
2， 递归算法必须能改变状态向基本结束条件演 进（减小问题规模)
3,递归算法必须调用自身 （解决减小了规模的相同问题)
#10进制转16 递归实现def to10_16(n):base=16base1='0123456789ABCDEF'if n<base:return str(n)else:return base1[n%base]+to10_16(n//base)a=to10_16(1234)print(a[::-1])#10进制转2def to10_2(n):base=2if n<base:return str(n)else:return str(n%base)+to10_2(n//base)a=to10_2(1234)print(a[::-1])#10进制转4def to10_4(n):base=4if n<base:return str(n)else:return str(n%base)+to10_4(n//base)a=to10_4(1234)print(a[::-1])
递归可视化：分形树:
海龟 螺旋：递归实现
# 海龟import turtlet=turtle.Turtle()# t.forward(100)#前进100def drawSporal(t,linelen):if linelen>0:t.forward(linelen)t.right(90)#右转90度drawSporal(t,linelen-5)drawSporal(t, 250)turtle.done()
分形树：
#分形树import turtledef tree(len):if len>5:t.forward(len)t.right(20)tree(len-15)t.left(40)tree(len-15)t.right(20)t.backward(len)t=turtle.Turtle()t.left(90)t.penup()t.backward(100)t.pendown()t.pensize(2)t.pencolor('green')tree(75)t.hideturtle()turtle.done()
贪心策略
因为我们每次都试图解决问题的尽量大的一部分对应到兑换硬币问题，就是每次以最多数量的最大面值硬币来迅速减少找零面值
记忆化搜索
对这个递归解法进行改进的关键就在于消除重复计算
我们可以用一个表将计算过的中间结果保存起来在计算之前查表看看是否已经计算过
这个算法的中间结果就是部分找零的最优解,在递归调用过程中已经得到的最优解 被记录下来
在递归调用之前,先查找表中是否已有部分找零 的最优解 如果有,直接返回最优解而不进行递归调用
如果没有,才进行递归调用
找零兑换问题
我们要对每种硬币尝试 1次,例如美元硬币体系 :
找零减去1分(penny)后,求兑换硬币最少数量(递归调用自身);
找零减去5分(nikel)后,求兑换硬币最少数量
找零减去10分(dime)后,求兑换硬币最少数量
找零减去25分(quarter)后,求兑换硬币最少数量 上述4项中选择最小的一个。
例如6：
1+n(6-1)=1+n(5-1)=1+n(4-1)=1+n(3-1)...合计5
=1
n(6)=1+n(6-5)=
记忆化搜索 自己打的
cionvalue=[1,5,10,25]konw=[0]*1000def rec(cion):if konw[cion]!=0:return konw[cion]elif cion in cionvalue:return 1else:b=[]for i in [c for c in cionvalue if c<=cion]:b.append(1+rec(cion-i))konw[cion] = min(b)return min(b)print(rec(63))print(konw)
找零兑换问题 : 递归解法改进代码
cion=[1,5,10,25]know=[0]*10000def rec(change):mincion=changeif change in cion:know[change]=1return 1elif know[change]>0:return know[change]else:for i in [c for c in cion if c<=change]:print(change,i)numcion=1+rec(change-i)if numcion<mincion:mincion=numcion#找到最优解，记录到表中know[change]=mincionreturn mincionprint(rec(16))
记忆化搜索 P1464 Function
对于一个递归函数w(a,b,c)w(a,b,c)
如果a \le 0a≤0orb \le 0b≤0orc \le 0c≤0就返回值11.如果a>20a>20orb>20b>20orc>20c>20就返回w(20,20,20)w(20,20,20)如果a<ba<b并且b<cb<c就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)其它的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)
这是个简单的递归函数，但实现起来可能会有些问题。当a,b,ca,b,c均为15时，调用的次数将非常的多。你要想个办法才行.
把return改成存在记忆化数组中 再后面函数后再加return
konw=[[[0]*200 for _ in range(200)] for _ in range(200)]def w(a,b,c):# print(a,b,c,an)if a<=0 or b <= 0 or c <= 0:konw[a][b][c]=1elif konw[a][b][c]!=0:return konw[a][b][c]elif a>20 or b >20 or c > 20:konw[a][b][c]=w(20,20,20)elif a<b and b<c:konw[a][b][c]= w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)else:konw[a][b][c]= w(a-1, b, c)+w(a-1, b-1, c)+w(a-1, b, c-1)-w(a-1, b-1, c-1)return konw[a][b][c]while True:a,b,c=list(map(int,input().split()))if a==-1 and b == -1 and c == -1:breakelse:w(a,b,c)print('w(%s, %s, %s) = %s'%(a,b,c,konw[a][b][c]))
动态规划
动态规划算法采用了一种更有条理的方式 来得到问题的解
找零兑换的动态规划算法从最简单的“1 分钱找零”的最优解开始,逐步递加上去 直到我们需要的找零钱数
在找零递加的过程中,设法保持每一分钱的递加都是最优解,一直加到求解找零钱 数,自然得到最优解
递加的过程能保持最优解的关键是,其依 赖于更少钱数最优解的简单计算,而更少 钱数的最优解已经得到了。
问题的最优解包含了更小规模子问题的最 优解,这是一个最优化问题能够用动态规 划策略解决的必要条件。
originalamount找零兑换问题具体来说就是 :
cionvalue=[1,5,10,25]konw=[0]*10000def dp(cion):for cent in range(1,cion+1):cioncout=centfor i in [c for c in cionvalue if c<=cent]:if konw[cent-i]+1<cioncout:cioncout=konw[cent-i]+1konw[cent]=cioncoutreturn konw[cion]print(dp(53))print(konw)5[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 2, 3, 4, 5, 0, 0, 0, 0,
改进版本：
cionvalue=[1,5,10,25]konw=[0]*10000def dp(cion):for cent in range(1,cion+1):cioncout=centb=0for i in [c for c in cionvalue if c<=cent]:b=min(cioncout,konw[cent-i]+1)konw[cent]=breturn konw[cion]print(dp(53))1 1 12 2 23 3 34 4 45 5 55 1 5 当konw[0]=0,所以更小6 2 66 2 6
博物馆大盗问题
dp[i][j-w[i]]+v[i]
W：背包最大负重，i：第i件物品
代码：
baowu=[None,{'w':2,'v':3},{'w':3,'v':4},{'w':4,'v':8},{'w':5,'v':8},{'w':9,'v':10}]max_w=20m={(i,w):0 for i in range(len(baowu)) for w in range(max_w+1)}for i in range(1,len(baowu)):for w in range(1,max_w+1):if baowu[i]['w']>w:m[(i,w)]=m[(i-1,w)]#map的上一行else:m[(i,w)]=max(m[(i-1,w)],m[(i-1,w-baowu[i]['w'])]+baowu[i]['v'])第i件宝物质量+上一行可用背包质量print(m[(len(baowu)-1,max_w)])for i in range(len(baowu)) :for w in range(max_w+1):print('{:<3}'.format(m[(i,w)]),end='')print()290 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 3 4 4 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 0 0 3 4 8 8 11 12 12 15 15 15 15 15 15 15 15 15 15 15 15 0 0 3 4 8 8 11 12 12 16 16 19 20 20 23 23 23 23 23 23 23 0 0 3 4 8 8 11 12 12 16 16 19 20 20 23 23 23 23 26 26 29
装箱问题
P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 ()
v=int(input())b=int(input())m=[[0]*(v+1) for _ in range(b+1)]n=[0]for i in range(b):n.append(int(input()))for i in range(1,b+1):for w in range(1,v+1):#背包空间if n[i]>w:m[i][w]=m[i-1][w]else:m[i][w]=max(m[i-1][w],m[i-1][w-n[i]]+n[i])#m[i][w]=max(m[i-1][w],m[i][w-n[i]]+n[i])print(v-m[b][v])for i in range(b+1):print(m[i])0[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8][0, 0, 0, 3, 3, 3, 3, 3, 8, 8, 8, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11][0, 0, 0, 3, 3, 3, 3, 3, 8, 8, 8, 11, 12, 12, 12, 15, 15, 15, 15, 15, 20, 20, 20, 23, 23][0, 0, 0, 3, 3, 3, 3, 7, 8, 8, 10, 11, 12, 12, 12, 15, 15, 15, 18, 19, 20, 20, 22, 23, 23][0, 0, 0, 3, 3, 3, 3, 7, 8, 9, 10, 11, 12, 12, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24][0, 0, 0, 3, 3, 3, 3, 7, 8, 9, 10, 11, 12, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
P1164 小A点菜
P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 ()
n, m = [int(i) for i in input().split()]a = [0]while len(a) < n:a.extend(map(int,input().split()))dp = [[0] * (m + 1) for i in range(n + 1)]for i in range(1,n+1):w = a[i]for j in range(0, m + 1):if j < w:dp[i ][j] = dp[i-1][j]elif j == w:dp[i ][j] = dp[i-1][j] + 1else:# print(j-w,i,j)dp[i ][j] = dp[i-1][j - w] + dp[i-1][j]print(dp[n][m])4 41 1 2 230 0 0 0 00 1 0 0 00 2 1 0 00 2 2 2 10 2 3 4 3
一维优化
P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 ()
t,m1=list(map(int,input().split()))yao=[None,]for i in range(m1):q,q1=list(map(int,input().split()))yao.append({'w':q,'v':q1})m=[[0]*(t+1)for _ in range(m1+1)]dp=[0]*(t+1)if m1==1:print(t//yao[1]['w']*yao[1]['v'])else:#二维# for i in range(1,m1+1):#for j in range(yao[i]['w'],t+1):# if yao[i]['w']>j:# m[i][j]=m[i-1][j]# else:# m[i][j]=max(m[i-1][j],m[i][j-yao[i]['w']]+yao[i]['v'])# print(m[m1][t])#一维for i in range(1, m1 + 1):# for j in range(t,yao[i]['w']-1,-1):for j in range(yao[i]['w'] , t+1):dp[j]=max(dp[j],dp[j-yao[i]['w']]+yao[i]['v'])print(dp[t])print(dp)140[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140]
小结
如果一个问题最优解包括规模更小相同问题的最优解,就可以用动态规划来解决
分割线
#分形树import turtledef tree(len):if len>5:t.forward(len)t.right(20)tree(len-10)t.left(40)tree(len-10)t.right(20)t.backward(len)t=turtle.Turtle()t.left(90)t.penup()t.backward(100)t.pendown()t.pensize(2)t.speed(888)t.pencolor('green')tree(100)t.hideturtle()turtle.done()
