dp動態規劃 === ---- #### 什麼是DP(Dynamic Programming)? ---- DP又被稱為動態規劃 透過把大問題拆成較簡單的子問題 求解複雜問題的方法 ---- dp利用記錄每個小問題的答案 減少重複計算 快速地找出最終的解 ---- 在寫dp時 我們要考慮兩個東西 __邊界條件__ 和 __轉移式__ 在接下來會詳細說明 --- ### 線性dp ---- 線性dp是學dp的起點 在這裡我們再拿費氏數列來舉例 ---- ### 費氏數列 $f(n)=f(n-1)+f(n-2)$ n>=2 $f(0)=1$ $f(1)=1$ ---- 在費氏數列中 他的邊界條件就是 $dp[0]=1$ $dp[1]=1$ 轉移式就是 $dp[i]=dp[i-1]+dp[i-2]$ ---- 實際寫出來就會長這樣 ```cpp= int dp[20005]; dp[0]=1; dp[1]=1; for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2]; cout<<dp[n]; ``` ---- 除了剛才那種寫法 我們還能用遞迴來寫 ---- ```cpp= int dp[200005]; int fibo(int i){ if(i==0 or i==1) return 1; if(dp[i]) return dp[i]; return dp[i]=fibo(i-1)+fibo(i-2); } ``` --- 剛才那兩個寫法 一種叫buttom-up 另一種叫top-down 兩種寫法各有優缺點 ---- ### buttom-up buttom-up通常用for迴圈來寫 顧名思義是從下到上來找出答案 優點是較遞迴來的快 缺點是沒那麼直觀 大部分的人dp都用這種方法來解 ---- ### top-down top-down一樣從名字來看就是從上到下 通常用遞迴來寫 優點是較直觀 缺點是多次呼叫函式會浪費時間 --- ### 練習題 [爬樓梯問題之一](http://mdcpp.mingdao.edu.tw/problem/A048) [爬樓梯問題之二](http://mdcpp.mingdao.edu.tw/problem/A049) [爬樓梯問題之三](http://mdcpp.mingdao.edu.tw/problem/A050) --- dp也能處理 __尋照最佳解的問題__ 拿[P-4-13. 最大連續子陣列](https://judge.tcirc.tw/ShowProblem?problemid=d052)來做講解 ---- 這題說給一個陣列 要找出總和最大的連續子陣列 我們來想想有什麼辦法 ---- 在還沒學dp前 我們只能枚舉所有左界和右界 列出所有可能後加起來 如果不用前綴和 時間複雜度會來到$O(N^3)$ 就算用了複雜度只會降到$O(N^2)$ $N$最大是$10^5$所以會 __TLE__ ---- 這時候我們就可以用dp了 首先要想 $dp[i]$所代表的意義 ---- 假設我們讓$dp[i]$的值是 __到$i$為止最大連續子陣列的和__ 那你會發現你想不出轉移式 ---- 所以我們要讓$dp[i]$是 __以$i$結尾最大的連續子陣列__ 這樣的話轉移式就是 $dp[i]=max(dp[i-1]+a[i],a[i])$ 邊界條件就是 $dp[0]=0$ 時間複雜度是$O(N)$ ---- code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; signed main(){ ios::sync_with_stdio(0);cin.tie(0);//IO優化 int n,a[N],dp[N]; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; dp[0]=0;//邊界條件 for(int i=1;i<=n;i++){ dp[i]=max(dp[i-1]+a[i],a[i]);//轉移式 } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dp[i]);//找最大值 cout<<ans; } ``` --- ## 二維DP ---- 二維dp就是dp那個陣列變二維 來看一下這個題目[採果實問題](http://mdcpp.mingdao.edu.tw/problem/A052) ---- 用dp來想 $dp[i][j]$代表走到i,j時能採到最多個果實數 邊界條件就都設0 轉移式是$dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]$ ----  ---- code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long const int N=200+5; signed main(){ ios::sync_with_stdio(0);cin.tie(0);//IO優化 int n,a[N][N],dp[N][N]={0}; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];//轉移式 cout<<dp[n][n]; } ``` ---- ### 練習題 [方格棋盤路線](https://judge.tcirc.tw/ShowProblem?problemid=d069) [投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373) --- ### 背包DP 背包dp有 - 01背包 - 有限背包 - 無限背包 ...很多種 我們這次先講01背包 ---- 01背包基本上會給 - 背包容量 - 物品重量 - 物品價值 最後會問裝出價值最高的價值 ---- 範例題 [裝貨櫃問題](https://zerojudge.tw/ShowProblem?problemid=b184) ---- 最簡單的方法就是用暴力枚舉 每種物品可拿可不拿 所以有$2^N$種可能 時間複雜度$O(2^N)$ N到26就不行了 ---- 這時候就要用dp了 我們開一個二維dp $dp[i][j]$代表 考慮到第$i$種物品時 最大容量為$j$時能裝的最大利潤 ---- 轉移式： $dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$ $w[i]$為第$i$項物品的重量 $v[i]$為第$i$項物品的價值 須注意$j-w[i]$可能小於0所以前面需要加條件式 避免溢位 ---- code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long signed main(){ ios::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ vector<int> v(n+1),w(n+1); vector<vector<int> > dp(n+1,vector<int>(101)); for(int i=1;i<=n;i++){ cin>>w[i]>>v[i]; } for(int i=1;i<=n;i++){ for(int j=0;j<=100;j++){ if(j-w[i]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); else dp[i][j]=dp[i-1][j]; } } cout<<dp[n][100]<<"\n"; } } ``` --- ### 背包dp優化 ---- 其實背包dp不用開到2維 開一維就夠了 只是這樣遍歷容量時要倒著走 ---- code ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long signed main(){ ios::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ vector<int> v(n+1),w(n+1); vector<int> dp(101); for(int i=1;i<=n;i++){ cin>>w[i]>>v[i]; } for(int i=1;i<=n;i++){ for(int j=100;j>0;j--){ if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[100]<<"\n"; } } ``` ---- ### 練習題 [置物櫃出租](https://judge.tcirc.tw/ShowProblem?problemid=d075) [D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)