分析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))