# dp經典題目
主要說一些dp的經典問題
=_=
## 最大子段和(Maximum Subarray)
例題
https://www.luogu.com.cn/problem/P1115
給你一個序列
當中有正有負
找出一段連續的子序列
其中這個子序列中的和為所有子序列中最大的
### 講解
#### <font color="##FF0000">**方法一:**</font>暴力解
用一個類似雙指針的方法
先用第一個當左指針
右指針一直向右移動直到碰到右界
左界右移
一直下去
每次掃完比較是不是最大值
這樣是可以的
只是很醜
而且超慢O(n^3)
#### <font color="#FF0000">**方法二:**</font>O(n)解
建立一個dp陣列跟一個arr陣列
arr[i]用來記錄第i個值
dp[i]中的值代表在<font color="##FF0000">結尾為i的時候的最大值</font>
這樣說太抽象
拿一個例子說明
<font color="#FFFFFF">_____</font>0. 1. 2. 3. 4. 5. 6.
arr=[2 -4 3 -1 2 -4 3]
**第一步:先設定結尾為index=0**
此時最大值為2
開頭結尾都是自己
<font color="#46A3FF">那紀錄dp[0]=2</font>
繼續下一步
**第二步:設定結尾為index=1**
此時可能出現以下情況:
<font color="#FF8040">**狀況一**:</font>2當頭-4當尾-->為-2
<font color="#FF8040">**狀況二**:</font>-4當頭而且-4當尾-->為-4
要選最大的
所以選狀況一的答案-2
<font color="#46A3FF">那紀錄dp[1]=-2</font>
好像感覺不出什麼東西
繼續看
**第三步:設定結尾為index=2**
此時可能出現以下情況:
<font color="#FF8040">**狀況一**:</font>2當頭3當尾-->為1
<font color="#FF8040">**狀況二**:</font>-4當頭3當尾-->為-1
<font color="#FF8040">**狀況三**:</font>3當頭而且3當尾-->為3
一樣選最大的3
<font color="#46A3FF">那紀錄dp[2]=3</font>
還是感覺不出什麼東西
**第四步:設定結尾為index=3**
<font color="#FF8040">**狀況一**:</font>2當頭-1當尾-->為0
<font color="#FF8040">**狀況二**:</font>-4當頭-1當尾-->為-2
<font color="#FF8040">**狀況三**:</font>3當頭-1當尾-->為2
<font color="#FF8040">**狀況四**:</font>-1當頭而且-1當尾-->為-1
一樣選最大的2
<font color="#46A3FF">那紀錄dp[3]=2</font>
繼續下去
最後dp會變:
dp[2 -2 3 2 4 0 3]
答案為4
你可能沒看出來
其實轉移式就是
>$$dp[i]=max(arr[i],arr[i]+dp[i-1])$$
白話就是結尾為i的最大值可能就是自己一個人
或者是自己加上**以自己前一個為結尾所得到的最大值**
用上面的例子:
```
dp[0]=max(2,2) ->2
dp[1]=max(-4,-4+dp[0]) ->-2
dp[2]=max(3,3+dp[1]) ->3
dp[3]=max(-1,-1+dp[2]) ->2
dp[4]=max(2,2+dp[3]) ->4(answer)
dp[5]=max(-4,-4+dp[4]) ->0
dp[6]=max(3,3+dp[5]) ->3
```
看不懂的話可以看這個
有字幕
https://www.youtube.com/watch?v=2MmGzdiKR9Y&ab_channel=BackToBackSWE
### 範例練習
洛谷:P1115 最大子段和
https://www.luogu.com.cn/problem/P1115
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 2e18
#define maxn 200005
#define mod 1000000007
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int dp[maxn]; //紀錄在結尾為i的時候的最大值
int arr[maxn]; //紀錄陣列中的值
int max_value=-2147483647; //不要設0
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
for(int i=1;i<=n;i++){
dp[i]=max(arr[i],arr[i]+dp[i-1]);//紀錄在結尾為i的時候的最大值
max_value=max(max_value,dp[i]);
}
cout<<max_value;
}
```
## 01背包問題
例題
https://zerojudge.tw/ShowProblem?problemid=b184
01背包問題-每種物品個數有只有1個
每個物品都有重量
每個只能取一次
問:在背包容量有限制時能拿走最大的價值
還有其他變化題
可以看:https://hackmd.io/1nEXxuhLTUCaTuYhYMTFhg
### 講解
先把接著要用到的變數規定好
value | 價值
--- | ---
**weight**|**重量**
只考慮第1到i項物品，背包體積為n時的最大價值，紀錄為:
$$dp[i][n]$$
假設固定體積n的背包，且有k種物品考慮
可寫成(偽程式碼):
```cpp=
for(int i=0;i<k;i++){
for(int j=0;j<n;j++){
if(n>=weight[i]){
dp[i][n]=max(dp[i-1][n],dp[i-1][n-weight[i]]+value[i]);
}
else{
dp[i][n]=dp[i-1][n];
}
}
}
```
不過有這樣空間複雜度很大
要減少空間複雜度可以用滾動dp
我們可以把轉移式寫成:
>$$dp[j]=max(dp[j],dp[j-weight[i]+value[i])$$
這樣不只空間複雜度變小很多
轉移式看起來也更乾淨易懂了
以下模板為偽程式碼
```cpp=
for(int i=0;i<物品數量;i++){
for(j=背包最大承重;j>0;j--){
if(j-weight[i]>=0){ //講白話一點:背包還能裝東西就更新
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); //dp[j]表示在背包最大承重為j時所能有的最大價值
}
}
}
```
### 範例練習
zerojudge:b184: 5. 裝貨櫃問題
https://zerojudge.tw/ShowProblem?problemid=b184
AC(2ms, 336KB)
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 1e9
#define maxn 10000005
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
int w=100;
while(cin>>n){
int weight[105];
int value[105];
int dp[105]={0};
for(int i=1;i<=n;i++){
cin>>weight[i]>>value[i];
}
for(int i=1;i<=n;i++){
for(int j=100;j>0;j--){
if(j-weight[i]>=0){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
}
cout<<dp[100]<<endl;
}
}
//b184
```
UVa:10130 - SuperSale
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1071
zerojudge:f440: 10130 - SuperSale
https://zerojudge.tw/ShowProblem?problemid=f440
(700ms)
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 1e12
int value[1005];
int weight[1005];
int dp[1005];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int k;
cin>>k;
for(int i=1;i<=k;i++){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>value[i]>>weight[i];
}
int m;
cin>>m;
int cnt=0;
while(m--){
int v;
cin>>v;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=v;j>0;j--){
if(j-weight[i]>=0){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
}
cnt+=dp[v];
}
cout<<cnt<<endl;
}
}
```
## 有權重的工作排程問題(interval scheduling problem)
例題
https://www.spoj.com/problems/RENT/
給一些工作的起始跟持續時間
但工作獲得的收益不一定相同
問最大獲得的收益為多少
### 講解
跟這個有點類似
https://hackmd.io/Ie1re-PuQiOGxqyxCRDgPg?view#%E6%8E%92%E7%A8%8B%E5%95%8F%E9%A1%8C%E6%B4%BB%E5%8B%95%E9%81%B8%E6%93%87%E5%95%8F%E9%A1%8C%EF%BC%88activity-selection-problem%EF%BC%89
不過每個工作的權重不再是一樣了
不過有個類似的想法就是**最早結束就排前面**
可是要找最優解要怎麼找
對就是dp
用目前的最優解往下推之後的最優解
可以這樣想
時間盡量不要浪費
盡可能銜接起來
所以建立一個陣列紀錄
看不懂就看這
https://www.youtube.com/watch?v=YMdnGChsvvo&t=885s&ab_channel=VivianNTUMiuLab
### 範例練習
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 2e18
#define maxn 100005
#define mod 1000000007
struct order{
int start,finish,value,index;
}orderlist[maxn];
bool cmp(order a,order b){
return a.finish<b.finish;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
int dp[maxn];
dp[0]=0;
int prev[maxn];
while(t--){
memset(dp,0,sizeof(dp));
memset(prev,0,sizeof(prev));
int n;
cin>>n;
for(int i=1;i<=n;i++){
int duration;
cin>>orderlist[i].start>>duration>>orderlist[i].value;
orderlist[i].finish=orderlist[i].start+duration;
}
sort(orderlist+1,orderlist+n+1,cmp);
for(int i=1;i<=n;i++){
orderlist[i].index=i;
}
for(int i=n;i>0;i--){
for(int j=n-1;j>0;j--){
if(orderlist[j].finish<=orderlist[i].start){
prev[i]=orderlist[j].index;
break;
}
}
}
for(int i=1;i<=n;i++){
dp[i]=max(dp[i-1],dp[prev[i]]+orderlist[i].value);
}
cout<<dp[n]<<endl;
}
}
```
Sign in with Wallet
Connect another wallet