# 動態規劃 DP ## 4/12社課 --- ## 什麼是DP? 用"表格"把運算結果紀錄下來利用 避免重複計算 可分為填表法(Bottom Up) 和遞迴法(Top Down) ---- ## 怎麼用DP? - 拆解題目 把題目分成小部分 - 重複運算(如遞迴)的地方用表格紀錄 - 如果題目給的數字太大記得用long long ---- ### 以DP角度來分析題目 - 定義狀態 - 列轉移式 - 定義初始狀態 ---- ## 狀態 通常指在程式中會變動的參數 題目的每個解都是一種狀態 ---- ## 轉移式 描述每個狀態之間的關聯(如遞迴) 轉移過程可以取用運算過的值求新值 ---- ## 定義初始狀態 就是設定遞迴的初始值 讓遞迴能運作 ---- ## DP複雜度 狀態數*轉移式複雜度 (太複雜的就大概估算就好) --- ## 為什麼需要DP 有紀錄跟沒紀錄運算量其實差很多! 當你TLE的時候就知道~~不能爆搜~~ ---- 舉個例子 以前費氏數列愛用的遞迴 假設需要算出f(100) 就得算出f(99)跟f(98) 如果推算下去 會有3*10²⁰次計算 其中佔最多數的就是重複運算 ##### (數據僅供參考) ---- 這時候DP就派上用場了 把運算結果紀錄後直接取用 就算是f(100000)也只要100000次 ~~好像還是很多~~ ---- 優先運算好的例子(Bottom Up) ```cpp= int dp(100); int main{ int i,num; dp[0]=dp[1]=1; //設初始值 for(i=2;i<100;i++) { dp[i]=dp[i-1]+dp[i-2]; //這裡直接先算好表格裡所有值 } cin >> n; cout << dp[n]; } ``` 也可以利用遞迴(Top Down)減少計算量 ---- ### 填表vs遞迴 大多數時候遞迴會比填表快 只取必要的值 如果題目會重複取值(多狀態)時 因遞迴會重複進函式 所以反而慢一些 --- ## 例題 ---- 假設有n階樓梯 一次可以走1階或2階 總共幾種方法? ---- 如果總方法數是f(n) 那走1階還會有n-1階 f(n-1)種方法 走2階則有f(n-2)種方法 所以總方法數是f(n)=f(n-1)+f(n-2)種 ---- ```cpp= long long dp[1000005]; int f(int n){ if(n<2) return 1; else{ if(dp[n]!=-1) return dp[n];//檢查dp[n]有沒有被計算過 dp[n]=f(n-1)+f(n-2);//算出dp[n]後存入表格 return dp[n]; } } int main{ int a; dp[1000005]={-1}; //如果是-1代表沒算過 while(cin >> a){ cout << f(n); } } ``` ---- 如果題目給的參數有兩個怎麼辦? - 把dp矩陣變成二維的 - 遞迴參數也改成兩個 ---- 回顧一下之前[社課](https://hackmd.io/@Alvin70812/dp#/2/4)的[骰子問題一](https://cses.fi/problemset/task/1633) 其實跟上面的樓梯問題很像 只是f(n)=f(n-1)+...+f(n-6) ---- 這題[骰子問題二](https://cses.fi/problemset/task/1725) 則是把參數變成兩個 f(投擲次數)(數字和)=1/6f(投擲次數-1)(數字和-k) k是指骰子投到的數字 利用遞迴把答案算出來 ---- 上面兩題已經有程式碼 所以就不再打一遍 ~~不是因為我懶~~ ---- [D038](https://zerojudge.tw/ShowProblem?problemid=d038) 這題也是費氏數列 ---- 牆壁長度為n n=1時有1種 n=2時有2種 長度為n時 會有f(n-2)+f(n-1)種 (n-2)的狀態補2塊磚塊 (n-1)的狀態補1塊直立磚塊 ---- ```cpp= #include <iostream> using namespace std; int main(int argc, char** argv) { int dp[52]={0,1,2}; int n; for(int i=3;i<=50;i++){ dp[i]=dp[i-1]+dp[i-2]; } while(cin>>n){ if(n==0)break; cout<<dp[n]<<"\n"; } return 0; } ``` --- ### 練習 [換零錢(d119)](https://zerojudge.tw/ShowProblem?problemid=d119) ---- 補充連結 [stringstream](https://hackmd.io/@Maxlight/rJwlvj8ad)