---
# System prepended metadata

title: dp經典題目

---

# 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;
    }
}
```