基本觀念
- 定義子問題。
- 找出問題與子問題之間的遞迴的方式進行計算。
- 找出子問題的計算順序來避免以遞迴的方式進行計算。
遞迴
如果依照遞迴的想法，可快速寫出下列程式:
| #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; |
| } |
但是我們真的需要這麼多的運算嗎?
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
| #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
| #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; |
| } |
題目連結
Frog1
- 給定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]+距離)\)
題目連結
Frog2
- 給定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\)
題目連結
[最小監控鄰居的成本]
- 給定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])\)
思路
- 我們定義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])\)
- 至於兩個都不選的情況無需特別判斷，因為其狀態是包含在只刪一個的狀態中。
思路
- dp[i]為第i點結束最常LIS長度
- \(j<i \; and \; s[j]<s[i]\)
- \(dp[i]=max(dp[j]+1)\)
優化
- 原複雜度\(O(n^2)\) -> \(O(nlogn)\)
- 數字較小結尾，lis數列越長
- lis數列具單調性，所以二分搜!!!
題目連結
背包問題
- 給定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]\)
題目連結
背包問題
- 給定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]\)
動態規劃
{"metaMigratedAt":"2023-06-16T21:04:32.904Z","metaMigratedFrom":"YAML","title":"動態規劃","breaks":true,"description":"定義子問題。","contributors":"[{\"id\":\"3978a08d-c47c-4560-b04d-dfbd8e71d0a3\",\"add\":24,\"del\":0},{\"id\":\"77be2af8-ce15-4578-9f4d-33dde9879cdc\",\"add\":4679,\"del\":1113},{\"id\":\"bafdb37c-3398-4b0c-b651-e39724d20cc3\",\"add\":1,\"del\":2},{\"id\":\"e071b978-bfdd-4b6f-b30a-0767dac744d2\",\"add\":1,\"del\":0}]"}