發揚多頭精神，質疑dp，理解dp，成為dp！

由淺入深

ATcoder Dp 普及~提高的版子記錄

Link

1. A - Frog 1
   和走樓梯很像的最優式dp
   發現每一個石頭只與前兩個有關，那么選取前兩個的dp值于高度差的和作動態調整即可
   轉移顯然\(O(1)\)

2. B - Frog 2
   這種題其實最優的是單調隊列，也就是P1725 琪露諾
   但是一般也會放數據結構過去，考慮區間查最大，可以做到\(\log n\)的轉移
   轉移\(O(1)\to\)單調隊列，\(O(\log n)\to\) ds

3. C - Vacation
   基礎的動態規劃概念
   記錄每天的三樣事情最優解，轉移從上一天不同的最優狀態轉移,顯然\(O(1)\)

4. D - Knapsack 1
   背包的版子題，背包的動規用一句話概括就是\(\to\) 該重量的最大價值
   對于所有物品去枚舉可能重量，\(n\times v\) 的復雜度，\(v\) 是最大重量

5. E - Knapsack 2
   轉換背包的動規思想，\(\to\) 得到該價值的最小重量
   那么只要重量比我小，我就可以取這個價值，這樣復雜度是 \(n\times w\)的，w是最大價值

6. F - LCS
   LIS問題，考慮對字符串dp，查了很多資料，在算法競賽中，LIS問題最多只能做到\(n\times m\)的
   其中 n，m是兩個串的長度，這個dp方程很版,要注意轉移順序
   其實也就是在i，j未完成匹配的最大匹配數

7. G - Longest Path
   這個東西是有向圖+沒有環
   那么拓撲序跑一遍，更新最長鏈即可

8. H - Grid 1
   這個一樣的，\(f_{i,j}=f_{i,j-1}+f_{i-1,j}\)
   由于只能向下向右，所以到這個點的路線數量就是來的總路線數量

9. I - Coins
   簡單概率dp入門題，考慮每次擲硬幣后正面朝上 \(k\) 個的概率
   方程就非常簡單\(f_{i}=f_{i-1}\times(p)+f{i}\times(1-p)\)
   每次這樣\(n^2\)遍歷一遍即可

10. J - Sushi
    期望dp入門題
    期望：概率乘上答案值的總和
    解釋一下吧

• 概率（Probability）
  描述某個事件發生的可能性大小，取值在\([0,1]\)。
  使用\(P(X)\)表示事件\(X\)發生的可能性
  比如拋一枚質地均勻的硬幣，正反兩面出現的可能性都是 \(\frac{1}{2}=0.5\)
  使用概率的說法就是 \(P(拋硬幣拋出正面)=0.5\)
  扔一枚六點骰子，那么就可以說 \(P(扔出1點)=\frac{1}{6}\)
• 期望(Expectation)
  期望是隨機變量取值的加權平均，權重是取該值的概率。
  對于離散隨機變量 \(X\) ,它的期望公式為 $E[X]=\sum_{k}k\times P(X=k) $
  什么叫離散隨機變量？
  就是這個事件可能出現的結果表達
  比如我們用 \(X=1\) 表示拋硬幣拋出了正面 ，\(X=0\) 表示拋出反面
  \(E[拋硬幣]=0\times P(拋出反面)+1 \times P(拋出正面)\)
  由于正反面概率相同，那么可以得出\(E[拋硬幣]=0\times 0.5+1\times 0.5=0.5\)
  也就是說,一直拋硬幣,正面為1,反面為0,最后加起來的平均數基本是0.5
  同理，我們用1,2,3,4,5,6表示擲骰子擲出六個數值
  \(E[擲骰子]=1\times \frac{1}{6}+2\times \frac{1}{6}+3\times \frac{1}{6}+4\times \frac{1}{6}+5\times \frac{1}{6}+6\times \frac{1}{6}=3.5\)
  也就是說,一直擲骰子,最后骰子上的值加起來的平均數基本是3.5
  期望反映的是長期重復試驗中隨機變量的平均結果。
• 區別
  期望求取要用到概率,而求概率不需要期望
  概率是具體結果的可能性,期望是長期平均值
• 結論
  期望是加權平均數,把結果乘上概率加起來就是期望了
• 例子的具體深入
  比如說這道題,也就是問你平均擲多少次骰子才可以把壽司吃完
  那么考慮開一個三維的\(f_{i,j,k}\)數組,表示還有 \(i\) 個1分盤, \(j\) 個二分盤, \(k\)個 三分盤的期望步數
  記住期望dp的重要建模套路,dp遞推!
  將當前狀態到目標結束所需要的期望次數分解成
• 當前一步(消耗1次)
• 從新狀態到結束狀態的期望次數
  \(E[當前狀態]=1+\sum_{新狀態}(P(轉移到新狀態)\times E[新狀態])\)
  本題以\(f_{i,j,k}\)作為狀態,新狀態有
  \(f_{i-1,j,k}\)(吃了一個1分裝)
  \(f_{i+1,j-1,k}\)(吃了一個2分裝)
  \(f_{i,j+1,k-1}\)(吃了一個3分裝)
  就可以得到方程了:

• 記住邊界條件是\(f_{0,0,0}\)
  遞推或是記搜都可以

11. K - Stones
    最簡單的博弈論遞推
    從小到大枚舉,如果這個點的所有轉移點都是必勝點,那么這個點就是比敗點,否則就是必勝點
    判斷一下就可以了

12. L - Deque
    最簡單的區間dp模板,考慮利用前綴和快速獲取一段區間的值
    那么會有非常明顯的dp方程,考慮取隊首隊尾的區別
    \(f_{l,r}=\max\begin{cases}sum_{l,r}-f_{l+1,r}&\\sum_{l,r}-f_{l,r-1}\end{cases}\)
    邊界條件就是\(f_{i,i}=a_i\)
    答案就是\(f_{1,n}-(sum_{1,n}-f_{1,n})\)

13. M - Candies
    前綴和優化dp的版子，先考慮最簡單的dp方程：
    \(f_{i,j}=\sum^{a_i}_{x=0}f_{i-1,j-x}\)
    發現每次搞sum累加很麻煩，前綴和優化即可）

14. N - Slimes
    模板，區間dp
    方程為\(f_{i,j}=\min{f_{i,j-1}+a_j,f_{i+1,j}+a_i}\)
    邊界條件為\(f_{i,i}=a_i\)

15. O - Matching
    狀壓版子，用01序列表示選了那些人，可以配成那些對

16. P - Independent Set
    簡單樹形dp版子
    用\(f_{u,0/1}\)表示該節點涂黑涂白的方案數，考慮合并子樹
    分討子樹不同涂色后乘起來就可以了

17. Q - Flowers
    線段樹優化轉移dp版子
    考慮到每次轉移只能從比自己小的節點傳過來，考慮權值線段樹存f值max

18. R - Walk
    矩陣優化dp版子
    每次最短路作floyd，相當于矩陣自乘
    考慮重載運算符快速冪即可

19. S - Digit Sum
    數位dp版子，考慮到d很小，所以對取模d作維護
    記得記憶化

20. T - Permutation

21. U - Grouping

22. V - Subtree

23. W - Intervals

24. X - Tower

25. Y - Grid 2

26. Z - Frog 3