# 動態規劃 # Dynamic Programming ---- ## 什麼是動態規劃？ ---- ### DP $\approx$ careful brute force ### DP $\approx$ subproblems + reuse ---- 講白話點就是 ### 算過的不要再算 --- ## 人生中的第一個 DP ### Fibonacci （費氏數列） ---- #### 設 $F(x)$ 為費氏數列第 $x$ 項 $F(1)=1$ $F(2)=1$ $F(x)=F(x-1)+F(x-2)$ , ($x>2$) ---- #### 直觀的算法 ```cpp= int F(int x){ if(x<=2) return 1; else return F(x-1)+F(x-2); } ``` 複雜度？ 差不多是 $O(2^\frac{N}{2})$ ---- #### 我們算了什麼  ---- #### 多算了什麼  ---- #### 一個更好的算法 存下已經算過的 ```cpp= const int N=100000; int dp[N+5]; int F(int x){ if(dp[x]) return dp[x]; else if(x<=2) return dp[x]=1; else return dp[x]=F(x-1)+F(x-2); } ``` 複雜度？ 大約是 $O(N)$ ---- #### 正常的寫法 ```cpp= const int N=100000; int dp[N+5]; void pre(){ dp[1]=1; dp[2]=1; for(int i=3;i<=N;i++){ dp[i]=dp[i-1]+dp[i-2]; } } int F(int x){ return dp[x]; } ``` 複雜度？ $O(N)$ --- ## 解決 DP 問題的步驟 1. 觀察性質 2. 設定狀態 3. 推出轉移式 4. AC ! ! ! ---- ### 觀察性質 #### 嗯... 這好像只能靠 ~~通靈~~ 經驗 注意一下測資大小， 從可能的複雜度出發，思考算法 ---- ### 設定狀態 大部分的情況，狀態 $=$ 題目問的答案 以費氏來說，$dp[i]$ 就是第 $i$ 項的答案 ---- ### 推出轉移式 先思考最簡單的狀態（基本元素） 透過觀察出來的性質，決定轉移式 ---- #### 好抽象... ---- ### 請前往 [動態規劃經典題](https://hackmd.io/@Paul-Liao/HkiyALOaO#/) --- ### 接下來就是刷題時間啦 ### 祝大家CF都上紅 ---- ### [Atcoder DP Contest](https://atcoder.jp/contests/dp/tasks) ---- ### [CSES](https://cses.fi/problemset/) 這個網站很適合練新技能 大部分都是裸題 ---- 接下來是幾題比較有挑戰性的題目 可以試著想想看，想不出來就看看題解吧 應該會有許多收穫 ---- ### [CF 1525D Armchairs](https://codeforces.com/problemset/problem/1525/D) ### [CF 1509C The Sports Festival](https://codeforces.com/contest/1509/problem/C) ### [ABC 159 F-Knapsack for All Segments](https://atcoder.jp/contests/abc159/tasks/abc159_f) ### [ABC 163 E-Active Infants](https://atcoder.jp/contests/abc163/tasks/abc163_e) --- ### 歡迎補充