内容简介：本文小编给大家详细分析了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))
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
计算机程序设计艺术：第4卷 第4册（双语版）
Donald E.Knuth / 苏运霖 / 机械工业出版社 / 2007-4 / 42.00元
关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在书中所表现出的博学、清晰、精确和高度幽默而对他无比敬仰。 为开始后续各卷的写作并更......一起来看看 《计算机程序设计艺术：第4卷 第4册（双语版）》 这本书的介绍吧!
