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

xialong 发布于2019-07-31 11:03 / 3251人阅读

摘要：概要本文只是简单的介绍动态规划递归非递归算法实现案例一题目一求数组非相邻最大和题目描述在一个数组中，找出一组不相邻的数字，使得最后的和最大。

概要

本文只是简单的介绍动态规划递归、非递归算法实现

案例一 题目一:求数组非相邻最大和

[题目描述]
在一个数组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))

引用

1，正月点灯笼-动态规划

私有云云服务器 python实现递归非递归遍历非递归先序 python中的递归

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44559.html

基本算法思想：递归+分治+动态规划+贪心+回溯+分支限界

摘要：代码实现见下面评论对应代码动态规划基本思想和分治法基本思想有共同的地方，不同的是子问题往往不是独立的，有事母问题要借助子问题的解来判断，因此把已经计算好的问题记录在表格中，后续如果需要查询一下，可以避免重复计算，这是动态规划的基本思想。作者：心叶时间：2018-05-01 19:28 本文对应github地址：https://github.com/yelloxing/... 以上实现...

EscapedDog 2019-08-26 11:52 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

Carson 2019-08-26 11:32 评论0 收藏0
动态规划法（八）最大子数组问题（maximum subarray problem）

摘要：动态规划法用表示最大子数组的结束下标为的情形，则对于，有这样就有了一个子结构，对于初始情形，遍历就能得到这个数组，其最大者即可最大子数组的和。动态规划法想法巧妙，运行效率也高，但是没有普遍的适用性。问题简介本文将介绍计算机算法中的经典问题——最大子数组问题（maximum subarray problem）。所谓的最大子数组问题，指的是：给定一个数组A，寻找A的和最大的非空连续...

jzman 2019-07-30 16:46 评论0 收藏0
看动画轻松理解「递归」与「动态规划」

摘要：程序员小吴打算使用动画的形式来帮助理解递归，然后通过递归的概念延伸至理解动态规划算法思想。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。难点就在于找出动态规划中的这三个概念。在学习「数据结构和算法」的过程中，因为人习惯了平铺直叙的思维方式，所以「递归」与「动态规划」这种带循环概念（绕来绕去）的往往是相对比较难以理解的两个抽象知识点。...

cnio 2019-07-30 18:41 评论0 收藏0