分析python动态规划的递归、非递归实现

栏目: 编程语言 · Python · 发布时间: 7年前

内容简介:本文小编给大家详细分析了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))


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

重来2

重来2

[美] 贾森·弗里德、[美] 戴维·海涅迈尔·汉森 / 苏西 / 中信出版社 / 2014-4-8 / 39.00元

“不再需要办公室”,这不仅仅是未来才有的事——它已经发生了。现在,轮到你迈开脚步,跟上时代的步伐了。 上百万的员工和成千上万的企业已经发现了远程工作的乐趣和好处。然而,远程工作方式还没有成为常见的选择。事实上,远程工作的技术手段都已齐备。还没有升级换代的,是人们的思想。 这本书的目的就是帮你把想法升级换代。作者会向你展示远程工作的诸多好处:可以找到最优秀的人才,从摧残灵魂的通勤路上解脱......一起来看看 《重来2》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具