安安 DP只是一種工具
也不是說遞迴的值存起來 多的是跟遞迴沒關係的DP解法
DP會說到遞迴基本上都是用費伯納契數列的入門
但有其他的像是01背包問題 就是一個DP比較泛用的例子
DP的重點在於
1. dp[i]定義
2. 狀態推導
費伯納契的dp[i]定義就是 費伯納契數列的第i+1個數
1, 1, 2, 3, 5, 8.....
因為費伯納契數列的數 就是該數前兩位相加 所以費伯納契dp[i]的狀態推導就是
dp[0] = 1, dp[1] = 1, 那dp[2] = dp[0]+dp[1] = 2
i>=2 dp[i] = dp[i-1] + dp[i-2]
dp[2] 為 費伯納契數列的第三個數 dp[3] 為第四個 依此列推
任何dp問題 只要把這兩個東西找出來 大概90%就完成了
像是01背包問題 dp[i] 就是 當背包空間為i的時候 背包內物品價值最高為多少
他的狀態推導 就是 dp[i] = max(dp[i], dp[i - volume[j]] + value[j]);
這個狀態推導有點跳 但意思就是說 背包空間為i 裝物品j的價值與不裝哪個高
舉個例子 假設我們 背包空間為50公升
分別有三個物品 每個物品只能放一次
物品A 20公升 價值為$10
物品B 30公升 價值為$5
物品C 50公升 價值為$20
那要怎麼裝 背包物品的價格會最高?
回到我們剛剛的狀態推導
dp[i] = max(dp[i], dp[i - volume[j]] + value[j]);
這邊我有點偷懶 用一維矩陣來算dp
所以需要一個小技巧就是從背包空間大到小 01背包問題因為物品只能被放一次
我們要從dp[50]開始
dp[50] = max(dp[50], dp[50-物品C體積]+物品C價值) = 20
只放物品C價值$20 因為物品C空間需要50 所以低於50我們都不用算了
break;
再來是跟放物品B比
dp[50] = max(dp[50]=20, dp[50-物品B體積]+物品B價值) 還是 只放物品C高
同時得到一個有意義的值 dp[49~30] 都是等於 $5
等等我們會用到
再來是跟放物品A比
dp[50] = max(dp[50]=20, dp[50-物品A體積]+物品A價值) 還是 只放物品C高
有趣的是這邊 dp[50] = max(dp[50], dp[50-20]+物品A價值)
dp[30]剛剛我們算過 是$5 就是只放物品B的價值 背包空間還有20 還夠放個物品A
那dp[30]+物品A的價值 就是 物品A+B的價值 = $15 還是比只放物品C低
最後我們得到 dp[50]當背包空間為50 物品價值最高為$20
這個簡單的例子 你用肉眼看就知道 只塞物品C價值最高 A+B也沒C高
但是當今天背包空間超大 物品幾千個 你人肉眼看不出來 算個老半天也算不出來
但是用一樣的dp[i]定義 一樣的狀態推導 背包從大到小
寫個小程式就能把答案算出來了
TLDR
DP只有兩個重點
1. dp[i]定義
2. 狀態推導
本巨巨祝福大家都能開開心心 輕輕鬆鬆學DP 謝謝大家
※ 引述《Nigger5566 (尼哥56)》之銘言：
: DP, Dynamic Programming 動態規劃
: 演算法的一個章節
: 大概就是把遞迴的值存起來不用重複迴
: 用嘴巴講的話滿簡單的
: 學會了DP可以幹嘛
: 能去Google上班嗎
: 有沒有八卦
: