Re: [問卦] 學會DP可以領多少？

安安 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上班嗎
: 有沒有八卦
:

--