概要

本文只是簡單的介紹動態規劃遞歸、非遞歸算法實現

案例一

題目一:求數組非相鄰最大和

[題目描述]

在一個數組arr中，找出一組不相鄰的數字，使得最后的和最大。

[示例輸入]

arr=1 2 4 1 7 8 3

[示例輸出]
15

from functools import wrapsdef memoDeco(func):  '''  memoDeco主要是緩存已遍歷的節點，減少遞歸內存開銷  '''  cashe={}  @wraps(func)  def wrapper(*args):    if args not in cashe:      cashe[args]=func(*args)    return cashe[args]    return wrapper@memoDecodef 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@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))