python遞歸算法案例_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))

引用