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

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

能用動態(tài)規(guī)劃解決的問題必須滿足未來與過去無關(guān)

例1

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

先來看看一般的方法是怎么做的

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

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

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

那就有請我們的動態(tài)規(guī)劃（DP）上場

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

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

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

得到通項公式

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

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

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

加強1

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

答案：

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

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

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

答案是=5985

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

將甲、乙、丙、丁、戊編號為1、2、3、4、5

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

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

那么有了最大限制呢？

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

DP解法：將甲、乙、丙、丁、戊編號為1、2、3、4、5

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

得到最終答案1486

如果在考試的時候遇到這么死媽的題，強烈建議DP，空間換取時間

例3??

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

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

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

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

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

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

得到

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

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

得到

最后留一個題哈，我沒時間寫了，過兩個周回來再發(fā)答案

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