内容简介:本文小编给大家详细分析了python动态规划的递归、非递归实现过程以及相关代码,有兴趣的朋友可以学习下。
概要
本文只是简单的介绍动态规划递归、非递归算法实现
案例一
题目一:求数组非相邻最大和
[题目描述]
在一个数组arr中,找出一组不相邻的数字,使得最后的和最大。
[示例输入]
arr=1 2 4 1 7 8 3
[示例输出]
15
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,2,4,1,7,8,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, index - 1, tar_num) or recSubSet(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比较方便 代码讲解详见引用一:正月点灯笼讲解 ''' 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] = subSet[i - 1, j] or subSet[i - 1, j - arr[i]] return subSet[-1, -1] if __name__ == "__main__": arr = (3, 34, 4, 12, 5, 3) tar_num = 13 print(dpSubSet(arr, tar_num))
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
精通CSS(第2版)
[英] Andy Budd、[英] Simon Collison、[英] Cameron Moll / 陈剑瓯 / 人民邮电出版社 / 2010-5 / 49.00元
本书汇集了最有用的CSS技术,介绍了CSS的基本概念和最佳实践,结合实例探讨了图像、链接和列表的操纵,还有表单设计、数据表格设计、纯CSS布局等核心CSS技术。此外,书中着眼于创建跨浏览器的技术,讨论了bug及其捕捉和修复技术,还将所有技术组合成两个精彩的实例,讲述这些技术的工作原理和实际用法。 本书适合具有HTML和CSS基础知识的读者阅读。一起来看看 《精通CSS(第2版)》 这本书的介绍吧!
在线进制转换器
各进制数互转换器
UNIX 时间戳转换
UNIX 时间戳转换