动态规划是运筹学的一个分支，是求解决策过程最优化的过程。身为六大算法之一，时常出现在笔试题中。
试题1
试题1：时间规划题，每项任务都有自己的开始时间和结束时间以及相应的收益。用户可以自主选择完成的任务，横坐标表示时间，红字表示收益，问用户如何选择任务的执行可以获得最高的收益
该问题可以通过简单的选或者不选的思路来进行解决，如我优先考虑第8个任务，如果选了第8个任务，那我的收益就是4+前5个任务中的最优解，如果不选第8个，那我的收益就是前7个任务的最优解，递归式描述如下
OPT(8)=max(4+OPT(5),OPT(7))
有了递归式，整个问题就好解决了很多，同时我们也发现，这样的递归与斐波拉契数列非常相似。而在斐波拉契数列中，存在着重复求解子结构的现象。所以，最好的办法是从0开始进行计算，记录每一个OPT的值以减少时间复杂度。
试题2：选择1、2、4、1、7、8、3中的数字，要求不能选择相邻的数字，使得选择数字的和最大
OPT(i)=max(arr[i]+OPT(i-2)、OPT(i-1))
OPT(0)=1 OPT(1)=max(arr[1]、OPT(0))
同样也是选或者不选的思路，递归的同时也可以选择动态规划来减少时间复杂度
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：从一组序列中选择子序列，使其和满足某个值，判断是否存在
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)
