不能放棄治療,每天都要進(jìn)步！！

什么時(shí)候使用動(dòng)態(tài)規(guī)劃呢？

1. 求一個(gè)問(wèn)題的最優(yōu)解

2. 大問(wèn)題可以分解為子問(wèn)題，子問(wèn)題還有重疊的更小的子問(wèn)題

3. 整體問(wèn)題最優(yōu)解取決于子問(wèn)題的最優(yōu)解（狀態(tài)轉(zhuǎn)移方程）

4. 從上往下分析問(wèn)題，從下往上解決問(wèn)題

5. 討論底層的邊界問(wèn)題

實(shí)例1：割繩子問(wèn)題

題目：給你一根長(zhǎng)度為n的繩子，請(qǐng)把繩子剪成m段 (m和n都是整數(shù)，n>1并且m>1)每段繩子的長(zhǎng)度記為k[0],k[1],…,k[m]. 請(qǐng)問(wèn)k[0]k[1]…*k[m]可能的最大乘積是多少？例如，當(dāng)繩子的長(zhǎng)度為8時(shí)，我們把它剪成長(zhǎng)度分別為2,3,3的三段，此時(shí)得到的最大乘積是18.

思路：f(n)=max{f(i)f(n-i)}，想發(fā)與實(shí)現(xiàn)是2個(gè)方法，想的時(shí)候是遞歸，實(shí)現(xiàn)的時(shí)候是從底層至最上面。

實(shí)現(xiàn)：1米最1，2米最大是2,3米最大是3,4米最大是4，依次類(lèi)推，求n米的最大切割

算法復(fù)雜度O（n2）

#-*- coding: utf-8 -*

defmaxCutString(length):#這三行代表輸入的繩子長(zhǎng)度為1,2,3時(shí)，發(fā)生切割動(dòng)作，最大的乘積

if length < 2:return0if length == 2:return 1

if length == 3：return 2

#繩子不斷切割，當(dāng)切割到長(zhǎng)度為1,2,3時(shí)，不能繼續(xù)切割，直接返回1,2.3

arr=[0,1,2,3]#記錄繩子長(zhǎng)度為i時(shí)候的最大乘積arr[i]

for i in range(4,length+1):

maxs=0for j in range(1,i/2+1):

mult=arr[j]*arr[i-j]if maxs

maxs=mult

arr.append(maxs)returnarr[length]print maxCutString(8）

View Code

實(shí)例2：最大連續(xù)子項(xiàng)和

思路：

實(shí)現(xiàn)：maxtmp記錄臨時(shí)子項(xiàng)和，遇到的每一個(gè)數(shù)不斷累加；當(dāng)maxtmp為負(fù)時(shí)，清空，從下一個(gè)數(shù)開(kāi)始，從新累加；當(dāng)累加的數(shù)大于maxsum時(shí)，將值賦給maxsum

復(fù)雜度：O(n)

#-*- coding: utf-8 -*#!usr/bin/python

defmaxSum(lists):

maxsum=0

maxtmp=0for i inrange(len(lists)):if maxtmp<=0:

maxtmp=lists[i]else:

maxtmp+=lists[i]if maxtmp >maxsum:

maxsum=maxtmpreturnmaxsum

lists=[1,3,-3,4,-6,5]print maxSum(lists)

View Code

還有一種暴力求解，雙層遍歷，復(fù)雜度O(n2)

#-*- coding: utf-8 -*#!usr/bin/python

defmaxSum(lists):

maxsum=0for i inrange(len(lists)):

maxtmp=0for j inrange(i,len(lists)):

maxtmp+=lists[j]if maxtmp >maxsum:

maxsum=maxtmpreturnmaxsum

lists=[1,3,-3,4,-6,5]print maxSum(lists)

View Code

實(shí)例3：放蘋(píng)果

把M個(gè)同樣的蘋(píng)果放在N個(gè)同樣的盤(pán)子里，允許有的盤(pán)子空著不放，問(wèn)共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。

思路：f(m,n) =f(m,n-1)+f(m-n,n)

設(shè)f(m,n) 為m個(gè)蘋(píng)果，n個(gè)盤(pán)子的放法數(shù)目，則先對(duì)n作討論，

當(dāng)n>m：必定有n-m個(gè)盤(pán)子永遠(yuǎn)空著，去掉它們對(duì)擺放蘋(píng)果方法數(shù)目不產(chǎn)生影響。即if(n>m) f(m,n) = f(m,m)

當(dāng)n<=m：不同的放法可以分成兩類(lèi)：

1、有至少一個(gè)盤(pán)子空著，即相當(dāng)于f(m,n) = f(m,n-1);

2、所有盤(pán)子都有蘋(píng)果，相當(dāng)于可以從每個(gè)盤(pán)子中拿掉一個(gè)蘋(píng)果，不影響不同放法的數(shù)目，即f(m,n) = f(m-n,n).

而總的放蘋(píng)果的放法數(shù)目等于兩者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)

遞歸出口條件說(shuō)明：

1.當(dāng)n=1時(shí)，所有蘋(píng)果都必須放在一個(gè)盤(pán)子里，所以返回１；

2.當(dāng)沒(méi)有蘋(píng)果可放時(shí)，定義為１種放法；

遞歸的兩條路，第一條n會(huì)逐漸減少，終會(huì)到達(dá)出口n==1;

第二條m會(huì)逐漸減少，因?yàn)閚>m時(shí)，我們會(huì)return f(m,m)　所以終會(huì)到達(dá)出口m==0

#!usr/bin/python

deff(m,n):if (m==0 or n==1):return 1

if m

lines=map(int,raw_input().strip().split())print f(lines[0],lines[1])

View Code

實(shí)例四：青蛙跳臺(tái)階問(wèn)題

1.如果青蛙可以一次跳 1 級(jí)，也可以一次跳 2 級(jí)。問(wèn)要跳上第 n級(jí)臺(tái)階有多少種跳法？

思路:f(n)=f(n-1)+f(n-2) 第n級(jí)別只能由n-1級(jí)別和第n-2級(jí)別的青蛙跳到

#-*- conding: utf-8 -*#遞歸解法

deff(n):if n==1:return 1

elif n==2:return 2

else:return f(n-1)+f(n-2)print f(8)#自下到上解法

deff2(n):

arr=[0,1,2]for i in range(3,n+1):

tmp=arr[i-1]+arr[i-2]

arr.append(tmp)returnarr[n]print f2(8)

View Code

2.如果青蛙可以一次跳 1 級(jí)，也可以一次跳 2 級(jí)，一次跳 3 級(jí)，…，一次跳 nn 級(jí)。問(wèn)要跳上第 n級(jí)臺(tái)階有多少種跳法？

#.*. coding:utf-8 -*#遞歸解法

deff(n):if n==1:return 1

else:return 2*f(n-1)print f(8)#自下而上解法

deff2(n):

arr=[0,1,2]for i in range(3,n+1):

tmp=2*arr[i-1]

arr.append(tmp)returnarr[n]print f2(8)

View Code

總結(jié)

以上是生活随笔為你收集整理的python动态规划详解_python----动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。