動態規劃中的階段，狀態是什麼？應該怎麼找？

1樓：KellyFrog

一般來說，狀態要包含當前的所有可能用到的資訊，比如揹包中的體積，如果發現有後效性（當前的狀態內的資訊會影響後面的決策）那就加一維，就是這麼簡單。

2樓：ChathFaern

我認為動態規劃裡的「規劃」其實是遞推的意思，只是每一步運用的遞推規則會根據情況而動態變化，因此動態規劃其實就是動態遞推。狀態方程就是動態遞推方程，由於動態遞推的規則比較複雜，尋找正確的狀態方程常常是困難的。

遞推演算法必須有乙個確定的初始值，而一字之差的遞迴演算法必須在某些確定的終止值返回。這提示我們，當直接尋找狀態方程比較困難時，可以嘗試從遞迴入手，反向建構動態規劃模型。直接建立狀態方程就是自底向上 (Bottom Up) 的動態規劃，從遞迴方程入手建構則是自頂向下（Top Bottom）的動態規劃。

自底向上動態規劃的「動態」體現在遞推規則上，而自頂向下動態規劃的「動態」體現在遞迴方程裡。

直接尋找狀態方程，沒有通用的辦法，但一般而言是從分析求解目標入手，提取可用於描述目標的乙個或多個引數作為狀態。

相比之下，遞推形式的動態規劃有更明確的操作流程。

1.建立暴力窮舉的遞推演算法；

2.分析執行過程，找出其中的重複步驟。這裡的重複步驟一般指的是前面的遞迴過程已經計算過，可以直接給出結果，卻多次重複計算的部分。

3.找出這些重複部分之後，把相應結果儲存在乙個合適的資料結構裡，遇到重複計算的時候直接返回結果，從而節省大量計算時間，這一步被稱為「記憶化「（Memoization）。記憶化之後，暴力窮舉的遞迴演算法就變成了乙個自頂向下的動態規劃演算法。

4.用來進行記憶化的資料結構，與狀態方程常常有密切聯絡。分析記憶化過程，嘗試將遞迴改為非遞迴，如能成功則得到自底向上的動態規劃模型。

3樓：見習程式猿ytr

我個人理解所謂狀態就是用來記錄的資訊。

理論上每乙個dp都可以用暴力方法做，那麼古爾丹，代價是什麼呢？

暴力方法會相對於dp有冗餘項，那麼實際上用空間來儲存資訊，避免冗餘就是dp的核心目的;

（然後留乙個坑我有空繼續編輯）

4樓：UltiMadow

dp沒有套路，真的沒有套路

多練就行了，洛谷上前五有三個dp題單，乙個偏簡單，乙個偏難，窩的算是中等難度，都做完基本就沒問題了/cy

5樓：redegg

動態規劃三個比較重要的東西：

狀態，轉移，初始狀態。

用最簡單的題目模型來說一下吧，給無數張70，30，40三種面值的貨幣，問可以湊出100元以內的哪些面值的錢。

狀態就是對題目模型的數學描述，比如我用f(x)表示我能否湊出x，f(100)=1表示我可以湊出100元，f(50)=0表示我沒法湊出50元。

找狀態需要多練題，很多都是經驗。

轉移的話，如果f(a)=1並且f(b)=1，那麼f(a+b)=1。

初始狀態，明顯是f(40)=f(30)=f(70)=1。

那麼我們可以根據上面，寫出乙個兩層列舉演算法，會進行10000次轉移。

當然我們可以進行優化，讓轉移中的b的取值範圍限定在30,40,70三個數，可以將轉移次數降低到300次。

然後得到的30,40,60,70,80,90,100。

6樓：suxxsfe

狀態就是找乙個好幾維的陣列，把能決定當前答案的資訊都裝在下標裡，缺少乙個都不能決定當前答案

比如揹包，當前答案是由「考慮到前幾個物品」和「剩餘空間」一起決定的，所以f[i][j]表示前i個物品還剩j個空間

再比如說，要求揹包k優解，那麼決定答案的就還有乙個當前是第幾優的解，所以f[i][j][w]表示第w優解

然後再做優化，比如那個i就可以去掉，這就根據每個題來了

你說的階段應該是指轉移？

轉移要求沒有後效性，就是說乙個狀態能轉移到另乙個狀態，就從這個被轉移的狀態向轉移到的狀態連個邊，如果無環就說明沒後效性可以dp

轉移一般兩種，乙個是知道到前狀態能轉移到哪些狀態，還有就是知道哪些狀態能轉移到當前狀態

後者一般用記憶話搜尋實現

如果有後效性，可能是把產生後效性的東西放在下標裡，就和狀壓dp有點像，但具體不太清楚

剛學dp肯定很懵，dp有點套路的感覺，比如好多題的狀態都有一維「考慮前i個XX」

所以應該做多了就好了

動態規劃中的階段，狀態是什麼？應該怎麼找？

動態規劃中的無後效性是什麼意思？

動態規劃和遞迴之間的關係是什麼？

計算機中的動態規劃對應的數學模型是什麼？

其他用戶還看了：