时间:2021-05-22
概要
本文只是简单的介绍动态规划递归、非递归算法实现
案例一
题目一:求数组非相邻最大和
[题目描述]
在一个数组arr中,找出一组不相邻的数字,使得最后的和最大。
[示例输入]
arr=1 2 4 1 7 8 3
[示例输出]
15
非递归实现
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@memoDecodef 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 npdef 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))声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方
Java实现单链表反转,递归和非递归两种形式/***反转单链表*//***定义链表**@author16026**/classNode{intval;Noden
主要是:前序遍历、中序遍历、后序遍历、层级遍历、非递归前序遍历、非递归中序遍历、非递归后序遍历复制代码代码如下:#!/usr/bin/envpython#-*-
本文实例讲述了python中尾递归用法。分享给大家供大家参考。具体分析如下:如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当
复制代码代码如下:采用递归形式和非递归形式实现斐波那契数列复制代码代码如下:#include"stdafx.h"#includeusingnamespacest