分析python动态规划的递归、非递归实现
概要
本文只是简单的介绍动态规划递归、非递归算法实现
案例一
题目一:求数组非相邻最大和
[题目描述]
在一个数组arr中,找出一组不相邻的数字,使得最后的和最大。
[示例输入]
arr=1241783
[示例输出]
15
fromfunctoolsimportwraps defmemoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) defwrapper(*args): ifargsnotincashe: cashe[args]=func(*args) returncashe[args] returnwrapper @memoDeco defrecMaxArray(array,index): ifindex==0: returnarray[0] elifindex==1: returnmax(array[0],array[1]) else: returnmax(recMaxArray(array,index-2)+array[index],recMaxArray(array,index-1)) if__name__=="__main__": array=(1,2,4,1,7,8,3) print(recMaxArray(array,len(array)-1))
非递归实现
defdpMaxArray(array): ''' 代码讲解详见引用一:正月点灯笼讲解 ''' lens=len(array) maxArray=[0]*(lens) maxArray[0]=array[0] maxArray[1]=max(array[0],array[1]) foriinrange(2,lens): maxArray[i]=max(maxArray[i-2]+array[i],maxArray[i-1]) returnmaxArray[-1] if__name__=="__main__": array=(1,2,4,1,7,8,3) print(dpMaxArray(array))
案例二
[题目描述]
给定一个正整数s,判断一个数组arr中,是否有一组数字加起来等于s。
[示例输入]
arr=33441253
s=9
[实例输出]
true
递归实现
fromfunctoolsimportwraps #和第一题一样,套用装饰器可以做一个缓存节点作用 defmemoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) defwrapper(*args): ifargsnotincashe: cashe[args]=func(*args) returncashe[args] returnwrapper @memoDeco defrecSubSet(arr,index,tar_num): ifindex==0: returnarr[0]==tar_num eliftar_num==0: returnTrue elifarr[index]>tar_num: returnrecSubSet(arr,index-1,tar_num) else: returnrecSubSet(arr,index-1,tar_num)orrecSubSet(arr,index-1,tar_num-index) if__name__=="__main__": arr=(3,34,4,12,5,3) tar_num=13 index=len(arr)-1 print(recSubSet(arr,index,tar_num))
非递归实现
''' 多维数组构建用python第三方库numpy比较方便 代码讲解详见引用一:正月点灯笼讲解 ''' importnumpyasnp defdpSubSet(arr,tar_num): subSet=np.zeros((len(arr),tar_num+1),dtype=bool) subSet[:,0]=True subSet[0,:]=False subSet[0,arr[0]]=True foriinrange(1,len(arr)): forjinrange(1,tar_num+1): ifarr[i]>j: subSet[i,j]=subSet[i-1,j] else: subSet[i,j]=subSet[i-1,j]orsubSet[i-1,j-arr[i]] returnsubSet[-1,-1] if__name__=="__main__": arr=(3,34,4,12,5,3) tar_num=13 print(dpSubSet(arr,tar_num))