詳解動态規劃

DP

詳解 \(DP\)

什麼是 \(DP\)？

動态規劃 \((Dynamic Programming ,DP)\) 就是将大問題轉化成小問題去處理。

動态規劃常常适用于有重疊子問題和最優子結構性質的問題

注意點一：

在 OI 中，計數等非最優化問題的遞推解法也常被不規範地稱作 DP

----OI Wiki

什麼是狀态？

狀态，用來描述某一問題的子問題的解。

什麼是狀态轉移方程？

狀态轉移方程是動态規劃中本階段的狀态往往是上一階段狀态和上一階段決策的結果。

---百度百科

簡單點來說，狀态轉移方程就是用來描述由之前狀态推出目前狀态的解的方程。如這道題目的 \(dp_i=dp_{i-1}+dp_{i-2}\)。

都有貪心了，為什麼還要 \(DP\)

貪心就是局部最優解就是全局最優解，但有些題目不是，舉個最簡單的栗子，數字三角形。

這道題目，對于每一次移動，我們不一定一定要移動到某一節點能移動到最大的，觀察樣例，如果按貪心算法，是 \(7 \rightarrow 8 \rightarrow 1 \rightarrow 7 \rightarrow 5\)，和是 \(28\) 但如果走 \(7 \rightarrow 3 \rightarrow 8 \rightarrow 7 \rightarrow 5\) 和就是 \(30\)！更大了！是以，這就是 \(DP\) 的重要性！

這道題目的狀态轉移方程：\(dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-1})+num_{i,j}\)。

兩種 \(DP\) 形式

我們可以用 我到哪裡去 和 我從哪裡來 兩種算法來解決 \(DP\)，第一個我到哪裡去是主動更新其他的狀态，而我從哪裡來其實就是剛才的，即通過之前的狀态的解被動更新自己的解。

記憶化搜尋

我們在進行搜尋的時候，經常會又“浪費”

就如斐波那契額數列，

int fib(int x){
if(x==1||x==2)return 1;
else return fib(x-1)+fib(x-2)
}
           

這個其實會有許多浪費，也就是說對于任意一個 \(fib_i\) 都會計算多次！那麼我們可以定義一個 \(visit\) 數組，表示這個是否計算過，在定義一個 \(fibo\) 數組，代表如果計算過它的值是多少，這個和并查集的路徑壓縮有一點點類似（注意是類似）。

題目推薦

• 數字三角形
• 過河卒
• 飛彈攔截
• LIS

背包問題

背包問題有很多種，篇幅有限，請大家到 OI Wiki上檢視。

優化

More