動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支尘喝，是求解決策過程最優(yōu)化的過程。身為六大算法之一斋陪，時(shí)常出現(xiàn)在筆試題中朽褪。
試題1
試題1：時(shí)間規(guī)劃題，每項(xiàng)任務(wù)都有自己的開始時(shí)間和結(jié)束時(shí)間以及相應(yīng)的收益鳍贾。用戶可以自主選擇完成的任務(wù)鞍匾，橫坐標(biāo)表示時(shí)間，紅字表示收益骑科，問用戶如何選擇任務(wù)的執(zhí)行可以獲得最高的收益
該問題可以通過簡(jiǎn)單的選或者不選的思路來(lái)進(jìn)行解決橡淑，如我優(yōu)先考慮第8個(gè)任務(wù)，如果選了第8個(gè)任務(wù)咆爽，那我的收益就是4+前5個(gè)任務(wù)中的最優(yōu)解梁棠，如果不選第8個(gè)，那我的收益就是前7個(gè)任務(wù)的最優(yōu)解斗埂，遞歸式描述如下
OPT(8)=max(4+OPT(5),OPT(7))
有了遞歸式符糊，整個(gè)問題就好解決了很多，同時(shí)我們也發(fā)現(xiàn)呛凶，這樣的遞歸與斐波拉契數(shù)列非常相似男娄。而在斐波拉契數(shù)列中，存在著重復(fù)求解子結(jié)構(gòu)的現(xiàn)象。所以模闲，最好的辦法是從0開始進(jìn)行計(jì)算建瘫，記錄每一個(gè)OPT的值以減少時(shí)間復(fù)雜度。
試題2：選擇1尸折、2啰脚、4、1实夹、7橄浓、8、3中的數(shù)字亮航，要求不能選擇相鄰的數(shù)字荸实，使得選擇數(shù)字的和最大
OPT(i)=max(arr[i]+OPT(i-2)、OPT(i-1))
OPT(0)=1 OPT(1)=max(arr[1]塞赂、OPT(0))
同樣也是選或者不選的思路泪勒，遞歸的同時(shí)也可以選擇動(dòng)態(tài)規(guī)劃來(lái)減少時(shí)間復(fù)雜度
python代碼如下
arr=[1,2,4,1,7,8,3]
opt=np.zero(len(arr))
opt[0]=1
opt[1]=2
for i in range(2,len(arr)):
A=opt[i-2]+arr[i]
B=opt[i-1]
opt[i]=max(A,B)
return opt[len(arr)-1]
試題3：從一組序列中選擇子序列，使其和滿足某個(gè)值宴猾，判斷是否存在
arr=[3,34,4,12,5,2]
def rec_subset(arr,i,s):
if s==0:
return True
if i==0:
return arr[0]==s
if arr[i]>s:
return rec_subset(arr,i-1,s)
else:
return rec_subset(arr,i-1,s-arr[i]) or rec_subset(arr,i-1,s)
