# 動態規劃 --- ## 基本觀念 1. 定義子問題。 2. 找出問題與子問題之間的遞迴的方式進行計算。 3. 找出子問題的計算順序來避免以遞迴的方式進行計算。 --- ## 範例(費式數列) ---- ### 遞迴 如果依照遞迴的想法，可快速寫出下列程式: ```cpp= #include<iostream> using namespace std; long long fib(int n){ if(n<3)return 1; return fib(n-1)+fib(n-2); } int main(){ int n; cin>>n; cout<<fib(n)<<'\n'; return 0; } ``` ---- 但是我們真的需要這麼多的運算嗎? ```graphviz digraph FIB{ nodesep=0.1 "fib(5)"->{"fib(3) " "fib(4)"} "fib(3) "->{"fib(1)" "fib(2)"} "fib(4)"->{"fib(2) " " fib(3) "} " fib(3) "->{" fib(1) " " fib(2) "} } ``` ---- ### Top-down memoization ```cpp= #include<iostream> using namespace std; long long dp[100005]; long long fib(int n){ if(dp[n]!=-1)return dp[n]; return dp[n]=fib(n-1)+fib(n-2); } int main(){ for(int i=0;i<100005;++i)dp[i]=-1; dp[1]=1,dp[2]=1; int n; cin>>n; cout<<fib(n)<<'\n'; return 0; } ``` ---- ### Bottom-up ```cpp= #include<iostream> using namespace std; long long fib[100005]; int main(){ fib[1]=1,fib[2]=1; int n; cin>>n; for(int i=3;i<=n;++i) fib[i]=fib[i-1]+fib[i-2]; cout<<fib[n]<<'\n'; return 0; } ``` --- ## 習題1 ---- ### 題目連結 [Frog1](https://atcoder.jp/contests/dp/tasks/dp_a) * 給定N個石頭，第i個石頭高度為$h_i$ * 第i個石頭只能跳到第i+1或第i+2個石頭 * 彈跳的費用為$|h_i-h_j|$，j為目的地 * 求到第n個石頭的花費最小值? * $2\le N \le 10^5$ ---- ### 思路 * $dp[i]$為走到第i格時最小的花費。 * $dp[i]=min(dp[i-1]+距離,dp[i-2]+距離)$ --- ## 習題2 ---- ### 題目連結 [Frog2](https://atcoder.jp/contests/dp/tasks/dp_b) * 給定N個石頭，第i個石頭高度為$h_i$ * 給定最遠距離K * 第i個石頭能跳到第i+1,i+2....,i+K個石頭 * 彈跳有費用為$|h_i,h_j|$，j為目的地 * 求到第n個石頭的花費最小值? * $2\le N \le 10^5$，$1\le K \le100$ ---- ### 思路 * $dp[i]$為走到第i格時最小的花費。 * $dp[i]$能由dp[i-1]....dp[i-k]組成，要考慮前面所有狀態值找到最小值 * $dp[i]=min(dp[j]+abs(fg[i]-fg[j]),dp[i])$ * $i-k\le j\le i-1$ --- ## 習題3 ---- ### 題目連結 [最小監控鄰居的成本] * 給定N個區塊，第i區塊監測花費為$c_i$ * 監控第i塊區間時，i-1和i+1塊區間也都會被監控 * 求所有區塊都能監視到的最小成本 * $N \le 10^5$ ---- ### 思路 * 這題看似和前面類似但dp[i-1]的值可能來自沒有挑選到i-1的值 * 定義$dp[i]$為必選i * $if$ $i>2$ * $dp[i] = c[i] + min(dp[i-1], dp[i-2], dp[i-3])$ --- ## 習題4 ---- ### 題目連結 [LCS] * 給定兩字串s1,s2 * 求其最長相同子字串 ---- ### 思路 * 我們定義dp[i][j]為s1的前i個字元和s2的前j個字元中，最長的lcs。 * $if$ $s1[i]==s2[j]$ * $dp[i][j]=dp[i-1][j-1]+1$ * $if$ $s1[i]!=s2[j]$ * $dp[i][j]=max(dp[i-1][j],dp[i][j-1])$ * 至於兩個都不選的情況無需特別判斷，因為其狀態是包含在只刪一個的狀態中。 ---- ### 挑戰題 [洛谷1439](https://www.luogu.com.cn/problem/P1439) --- ## 習題5 ---- ### 題目連結 [LIS] * 給定N個數，求數列中最常遞增子數列長度 ---- ### 思路 * dp[i]為第i點結束最常LIS長度 * $j<i \; and \; s[j]<s[i]$ * $dp[i]=max(dp[j]+1)$ ---- ### 優化 * 原複雜度$O(n^2)$ -> $O(nlogn)$ * 數字較小結尾，lis數列越長 * ex: 1 3 4 -> 1 2 4 * lis數列具單調性，所以二分搜!!! ---- ### 挑戰題 [洛谷P1091](https://www.luogu.com.cn/problem/P1091) --- ## 習題6 ---- ### 題目連結 [背包問題](https://atcoder.jp/contests/dp/tasks/dp_d) * 給定N個物品，第i個物品重量為$W_i$，價值$V_i$ * 背包容量為W * 求物品重量和不超過W，價值總和之最大值? * $1\le n \le 100$ , $1\le W \le 10^5$ ---- ### 思路 * dp[i][j]=只考慮前i個物品，背包容量為j的最大價值總和 * 考慮第i樣物品 * 選: $dp[i][j]=dp[i-1][j-W_i]+V_i$ * 不選: $dp[i][j]=dp[i-1][j]$ ---- ### 挑戰題 [knapsack2](https://atcoder.jp/contests/dp/tasks/dp_e) --- ## 習題7 ---- ### 題目連結 [背包問題](https://atcoder.jp/contests/dp/tasks/dp_d) * 給定N個物品，第i個物品重量為$W_i$，價值$V_i$ * 背包容量為W * 每樣物品無限制選取數量 * 求物品重量和不超過W，價值總和之最大值? * $1\le n \le 100$ , $1\le W \le 10^5$ ---- ### 思路 * dp[i][j]=只考慮前i個物品，背包容量為j的最大價值總和 * 考慮第i樣物品 * 選: $dp[i][j]=dp[i-1][j-W_i]+V_i$ * 不選: $dp[i][j]=dp[i-1][j]$ ---- ### 挑戰題 [knapsack2](https://atcoder.jp/contests/dp/tasks/dp_e) ---