分析python动态规划的递归、非递归实现
发布时间:2020-12-17 07:25:37 所属栏目:Python 来源:网络整理
导读:概要 本文只是简单的介绍动态规划递归、非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大。 [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wrapsdef memoDeco(fu
概要 本文只是简单的介绍动态规划递归、非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大。 [示例输入] arr=1 2 4 1 7 8 3 [示例输出] from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if args not in cashe: cashe[args]=func(*args) return cashe[args] return wrapper @memoDeco def recMaxArray(array,index): if index==0: return array[0] elif index==1: return max(array[0],array[1]) else: return max(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)) 非递归实现 def dpMaxArray(array): ''' 代码讲解详见引用一:正月点灯笼讲解 ''' lens=len(array) maxArray=[0]*(lens) maxArray[0]=array[0] maxArray[1]=max(array[0],array[1]) for i in range(2,lens): maxArray[i]=max(maxArray[i-2]+array[i],maxArray[i-1]) return maxArray[-1] if __name__=="__main__": array=(1,3) print(dpMaxArray(array)) 案例二 [题目描述] 给定一个正整数s,判断一个数组arr中,是否有一组数字加起来等于s。 [示例输入] arr=3 34 4 12 5 3 s=9 [实例输出] true 递归实现 from functools import wraps #和第一题一样,套用装饰器可以做一个缓存节点作用 def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe = {} @wraps(func) def wrapper(*args): if args not in cashe: cashe[args] = func(*args) return cashe[args] return wrapper @memoDeco def recSubSet(arr,index,tar_num): if index == 0: return arr[0] == tar_num elif tar_num == 0: return True elif arr[index] > tar_num: return recSubSet(arr,index - 1,tar_num) else: return recSubSet(arr,tar_num) or recSubSet(arr,tar_num - index) if __name__ == "__main__": arr = (3,34,12,5,3) tar_num = 13 index = len(arr) - 1 print(recSubSet(arr,tar_num)) 非递归实现 ''' 多维数组构建用python第三方库numpy比较方便 代码讲解详见引用一:正月点灯笼讲解 ''' import numpy as np def dpSubSet(arr,tar_num): subSet = np.zeros((len(arr),tar_num + 1),dtype=bool) subSet[:,0] = True subSet[0,:] = False subSet[0,arr[0]] = True for i in range(1,len(arr)): for j in range(1,tar_num + 1): if arr[i] > j: subSet[i,j] = subSet[i - 1,j] else: subSet[i,j] or subSet[i - 1,j - arr[i]] return subSet[-1,-1] if __name__ == "__main__": arr = (3,3) tar_num = 13 print(dpSubSet(arr,tar_num)) 您可能感兴趣的文章:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |