動(dòng)態(tài)規(guī)劃是什么？

baike.baidu.com/item/動(dòng)態(tài)規(guī)劃/529408?fr=aladdin

能用動(dòng)態(tài)規(guī)劃解決的問(wèn)題必須滿足未來(lái)與過(guò)去無(wú)關(guān)

例1

甲乙丙三個(gè)人傳球，現(xiàn)在球在甲手上，經(jīng)過(guò)5次傳球（球不能自己傳給自己），問(wèn)最終球傳回甲手里的路徑數(shù)目。

先來(lái)看看一般的方法是怎么做的

一條條數(shù)唄，總共10條。如果經(jīng)過(guò)稍微優(yōu)化，可以將乙和丙合并成一條權(quán)重為2的路徑

稍微優(yōu)化的算法，得到路徑數(shù)目為2x(2+1+2)=10

然而即使經(jīng)過(guò)優(yōu)化，此算法在傳遞次數(shù)更大的情況仍麻煩。

那就有請(qǐng)我們的動(dòng)態(tài)規(guī)劃（DP）上場(chǎng)

得狀態(tài)轉(zhuǎn)移方程

觀察表格得到規(guī)律：傳到甲手里得路徑數(shù)總是和其他人相差1

當(dāng)i為偶數(shù)時(shí)，甲多1；當(dāng)i為奇數(shù)時(shí)，甲少1；

得到通項(xiàng)公式

進(jìn)而無(wú)論傳幾次，傳到誰(shuí)手里，方案數(shù)都能很快地算出來(lái)。

容易推廣到m個(gè)人，傳n次，傳到自己手里的路徑數(shù)

傳到別人手里的路徑數(shù)

加強(qiáng)1

甲乙丙丁戊……共11人，球在甲手里，經(jīng)過(guò)100次傳球（球不能自己傳給自己），問(wèn)最終球傳回甲手里的路徑數(shù)目。

答案：

例2? ? ?甲乙丙丁戊五個(gè)桶，甲最多能裝5個(gè)球，乙最多能裝8個(gè)球，丙最多能裝11個(gè)球，丁最多7，戊最多3，現(xiàn)有17個(gè)完全相同的小球，問(wèn)裝進(jìn)5個(gè)桶中的方案數(shù)量（可空桶）。

先假設(shè)它沒(méi)有最大限制吧

削弱1? ?甲乙丙丁戊五個(gè)桶，現(xiàn)有17個(gè)完全相同的小球，問(wèn)裝進(jìn)5個(gè)桶中的方案數(shù)量（可空桶）。

答案是=5985

如果用動(dòng)態(tài)規(guī)劃解決呢?

將甲、乙、丙、丁、戊編號(hào)為1、2、3、4、5

狀態(tài)轉(zhuǎn)移方程

細(xì)心的人已經(jīng)發(fā)現(xiàn)了，這就是楊輝三角的表格版。用了DP反而更加麻煩了

那么有了最大限制呢？

傳統(tǒng)的辦法是分類討論，其實(shí)這已經(jīng)類似于DP了。

DP解法：將甲、乙、丙、丁、戊編號(hào)為1、2、3、4、5

狀態(tài)轉(zhuǎn)移方程

得到最終答案1486

如果在考試的時(shí)候遇到這么死媽的題，強(qiáng)烈建議DP，空間換取時(shí)間

例3??

M,N兩個(gè)暗箱。M中有3個(gè)黑球，N中有三個(gè)白球。將 “M，N各取一球并放到對(duì)方的箱子中”?執(zhí)行6次，問(wèn)最終M箱含3個(gè)白球的概率。

先把M和N可能的狀態(tài)列出來(lái)并標(biāo)號(hào)，用（a,b）表示a個(gè)黑球，b個(gè)白球

X只是一個(gè)代號(hào)，表示M和N所處的狀態(tài)。

用表示經(jīng)過(guò)次操作后M和N的狀態(tài)（特別地，為初態(tài)）

圖中紅色的4表示=1時(shí)=2的權(quán)重為4，即概率為

先來(lái)試試傳統(tǒng)的枚舉法

得到

枚舉法太容易漏情況了，我之前做就漏了倆個(gè)。

然后是動(dòng)態(tài)規(guī)劃的方法

得到

最后留一個(gè)題哈，我沒(méi)時(shí)間寫了，過(guò)兩個(gè)周回來(lái)再發(fā)答案

加強(qiáng)2? M、N兩個(gè)暗箱。M中有2個(gè)紅球，1個(gè)黃球；N中有1個(gè)黃球，3個(gè)藍(lán)球。將 “M、N各取一個(gè)球放到對(duì)方箱子中” 執(zhí)行5次。求最終M箱含1個(gè)紅球，2個(gè)藍(lán)球的概率。