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

来源：https://segmentfault.com/a/1190000013501780