文章目錄
- 動態規劃
- 動態規劃解題步驟
- 老生常談：湊零錢問題
- 其他和動歸相關篇章
動態規劃
動態規劃問題，它不叫動態規劃演算法，因為它不是一種演算法，它是一眾型別的問題的統稱，
我們前面兩篇的“遞回演算法”、“回溯演算法”，以及接下來會講的“貪心演算法”等都屬于動態規劃的范疇，
所以這一篇是會持續翻新的，每寫一種相關文章，都會在這里呈現出來，
那么，到底什么是動態規劃呢？
在現實生活中，有一類活動的程序，由于它的特殊性，可將程序分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個程序達到最好的活動效果，因此各個階段決策的選取不能任意確定，它依賴于當前面臨的狀態，又影響以后的發展，當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個程序的一潭訓動路線．這種把一個問題看作是一個前后關聯具有鏈狀結構的多階段程序就稱為多階段決策程序，這種問題稱為多階段決策問題，在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策依賴于當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最優化的程序為動態規劃方法 ，
動態規劃解題步驟
不扯那些彎彎繞的，
第一步：畫出暴力解法流程，
第二步：畫出決策樹（看著直觀）
第三步：寫出狀態轉移方程
第四步：決策樹剪枝
第五步：再優化：確定邊界
如果看了前面遞回那篇的話，這里就不難理解了，【C++】演算法集錦（2）：遞回精講
這五步列在這里，并不是說每一步都要嚴格的執行，我們的目標是解決問題，解決動態規劃問題就需要狀態轉移方程，要寫出好的狀態轉移方程就需要決策樹以及決策樹的剪枝優化，要畫出決策樹，最好有個暴力解的流程圖，
不要看不起暴力求解，動態規劃問題最困難的就是寫出狀態轉移方程，即這個暴力解，優化方法無非是用備忘錄或者 DP table，再無奧妙可言，
看一下上面遞回那篇，里面的“爬樓梯”栗子，
老生常談：湊零錢問題
先看下題目：給你 k 種?值的硬幣，?值分別為 c1, c2 … ck ，每種硬幣的數量無限，再給?個總金額 amount ，問你最少需要?枚硬幣湊出這個 金額，如果不可能湊出，演算法回傳 -1 ，
比方說 k=3，面值分別為：1,2,5，總金額：8，
那么我們該如何來解決這個問題？
?先，這個問題是動態規劃問題，因為它具有「最優子結構」的，
那么，既然知道了這是個動態規劃問題，就要思考如何列出正確的狀態轉移方程？
先確定「狀態」，也就是原問題和子問題中變化的變數，由于硬幣數量無限，所以唯?的狀態就是目標?額 amount ，
然后確定 dp 函式的定義：當前的?標?額是 n ，?少需要 dp(n) 個硬幣湊出該金額，
然后確定「選擇」并擇優，也就是對于每個狀態，可以做出什么選擇改變當 前狀態，具體到這個問題，無論當的?標金額是多少，選擇就是從面額串列 coins 中選擇?個硬幣，然后目標金額就會減少：
寫出一個暴力解法偽代碼：
def dp(n):
if n == 0: return 0
if n < 0: return -1
# 求最?值，所以初始化為正?窮
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# ?問題?解，跳過
if subproblem == -1: continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
?此，狀態轉移?程其實已經完成了：
畫出遞回樹看看：
下面點點點，
所以我們使用備忘錄來對決策樹進行剪枝操作（上面剪過了）
memo = dict()
def dp(n):
# 查備忘錄，避免重復計算
if n in memo: return memo[n]
if n == 0: return 0
if n < 0: return -1
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
if subproblem == -1: continue
res = min(res, 1 + subproblem)
# 記?備忘錄
memo[n] = res if res != float('INF') else -1
return memo[n]
當然，我們也可以自底向上使用 dp table 來消除重疊子問題， dp 陣列的定義和剛才 dp 函式類似，定義也是?樣的： dp[i] = x 表示，當目標金額為 i 時，至少需要 x 枚硬幣，
其他和動歸相關篇章
【C++】演算法集錦（2）：遞回精講
【C++】演算法集錦（3）：回溯，從入門到入土，七道試題精選、精講、精練
持續更新中，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/261773.html
標籤：其他