小編給大家分享一下python動態(tài)規(guī)劃的遞歸、非遞歸的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

為臨安等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及臨安網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站設(shè)計、做網(wǎng)站、臨安網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

概要

本文只是簡單的介紹動態(tài)規(guī)劃遞歸、非遞歸算法實現(xiàn)

案例一

題目一:求數(shù)組非相鄰大和

[題目描述]

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

[示例輸入]

arr=1 2 4 1 7 8 3

[示例輸出]
15

from functools import wraps
def memoDeco(func):
  '''
  memoDeco主要是緩存已遍歷的節(jié)點，減少遞歸內(nèi)存開銷
  '''
  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))

非遞歸實現(xiàn)

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))

案例二

[題目描述]

給定一個正整數(shù)s, 判斷一個數(shù)組arr中，是否有一組數(shù)字加起來等于s。

[示例輸入]

arr=3 34 4 12 5 3

s=9

[實例輸出]

true

遞歸實現(xiàn)

from functools import wraps

#和第一題一樣，套用裝飾器可以做一個緩存節(jié)點作用
def memoDeco(func):
  '''
  memoDeco主要是緩存已遍歷的節(jié)點，減少遞歸內(nèi)存開銷
  '''
  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))

非遞歸實現(xiàn)

'''
多維數(shù)組構(gòu)建用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))

以上是“python動態(tài)規(guī)劃的遞歸、非遞歸的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

分享文章：python動態(tài)規(guī)劃的遞歸、非遞歸的示例分析-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://chinadenli.net/article8/cojoip.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、品牌網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、搜索引擎優(yōu)化、品牌網(wǎng)站設(shè)計、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)