# 動態規劃(DP)

---

動態規劃（簡稱 DP）是一種運用遞迴解決問題的技巧。
它的應用廣泛，不像既有的演算法擁有固定流程，因此題目靈活多變，題型也千奇百怪

DP的核心概念就是避免對相同的問題再重複計算，而通常我們通常會使用陣列去存取已知的答案

## 實作

例題：
> 有一個 $N$ 階的樓梯，你站在第 $0$ 階上，每一步只能爬 $1$ 階或 $2$ 階，
且只能向上爬，不能往下走，求有多少種不同方法可以抵達第 $N$ 階？

國小數學告訴我們，不知道答案是多少，就把答案假設為未知數！

因此我們把到第$i$階的方法數設為$dp(i)$

考慮站在第 $i$ 階上，會有兩種可能：
->爬$1$階
->爬$2$階
同理到達第 $i$ 階的前一步，就只能是從第 $i - 1$ 階或第 $i - 2$ 階走上來的，
所以就把兩種的方法數加總就會得到第$i$階的方法數！

因此我們可以得到：
$$dp(i)=dp(i-1)+dp(i-2)$$
這其實就是費式數列

而如果把計算的過程畫成樹狀圖
就會發現，為了知道$dp(i)$，我們需要先知道$dp(i-1)$和$dp(i-2)$，
因此就相當於在樹上開分支。
而幾乎每個節點都會有兩個分支，因此會有約$2^n$個節點，
總時間複雜度就是$O(2^n)$！

這個複雜度當$n$很小時可能沒什麼影響，但$n$只要太大(大概到$30$就會爆了)保證吃TLE！

int f(int n){
    if(n == 1 || n == 0){
        return 1;
    }
    return f(n-1) + f(n-2);
}

---
### Top-down

透過觀察可以發現，我們重複計算了不少相同的值。

例如上圖中，$dp(2)$的值被計算了三次，

有沒有辦法把它壓到只有一次？

<br> <br/>
<br> <br/>
<br> <br/>
<br> <br/>

可以！

每次呼叫遞迴時，先檢查是否已計算過；如果有算過，直接回傳之前算好的結果。如果沒算過，就先計算它的值，然後在回傳之前把值填入表中，並標記這問題已算過。
(會優先往左子結點)

但須特別注意，如果**遞迴深度過深**，很有可能會因為Stack Overflow而吃到RE

//初始化
int dp[105] = {0};
dp[1] = 1;
dp[2] = 2;
int mod = 1e9+7;
int f(int n){
    if(dp[n] != 0){
        //查表並回傳結果
        return dp[n];
    }
    //標記並建表
    dp[n]=( f(n-1) + f(n-2) ) % mod;
    return dp[n];
}

時間複雜度:$O(N)$

---
### Bottom-up

如果每次都要遞迴到最底層，再依序回傳它的值，不如一開始就從底層開始算！
<!-- 通常使用迴圈實作，在求出關係式後，將子問題根據前面的計算結果進行結算 -->

<br><br/>


//初始化
int dp[105] = {0};
int mod = 1e9+7;
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= 100; i++){
    dp[i] = (dp[i-1] + dp[i-2]) % mod;
}

### 狀態轉移

透過「狀態」來定義要計算的問題，用來尋找和子問題之間的關係

那我們要如何定義狀態呢?

我們以剛剛的例題做為例子

通常會先將題目中所提及的變數套進DP式中，並且去定義該陣列所代表的涵義
->：$dp[i]$：代表走到第$i$階的方法數

接下來我們會通常會先考慮最後一格的情況，把所有可能的情況考慮過後，再把答案合併出來
-> $dp[i]=dp[i-1]+dp[i-2]$：代表第$i$階的前一格有可能是$i-1$或$i-2$階

最後記得要去定義初始狀態
->$dp[0]=1,dp[1]=1$ ： 走0步和1步都是一種可能
(該兩格狀態都無法用上述關係式找出答案)

### 增維

有時候會發現不管怎麼定義狀態都沒辦法描述完整，或著把不同情況視為相同狀態
很有可能是目前的維度不夠，導致無法表達出所有情況

而「增維」就是追加描述來區別這些不該被視為相同的狀況

----

而到目前為止講的概念單獨看時會太過抽象，也難以理解其用意
以下會搭配題目的實際應用，來解說每個概念

---

## 例題

換零錢問題$-1$
> 有大小為$N$的$A$序列，其中的每個數字代表的是硬幣面額，問有幾種方法可湊出S元
(前後順序不同視為不一樣，如1,2，2,1)

這題跟上一題樓梯很類似，只是現在有n種方式可以去挑選

#include <bits/stdc++.h>
using namespace std;
int n,s,a[105];
vector<int> dp(105, -1);

int f(int m){
    int ret = 0;
    if(m<0) return 0;
    for(int i=0;i<n;i++){
        if(m-a[i]>=0){//注意金錢不得為負
            if(dp[m-a[i]]!=-1){//如果表格被標記就直接使用
                ret+=dp[m-a[i]];
            }
            else{
                dp[m-a[i]]=f(m-a[i]);//標記並建表
                ret+=dp[m-a[i]];
            }
        }
    }
    return ret;
}
int main(){
    dp[0]=1;//初始化
    cin>>n>>s;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<f(s)<<"\n";
return 0;
}

換零錢問題$-2$
> 有大小為$N$的$A$序列，每個數字代表的是硬幣面額，並且不重複挑選，問有幾種方法可湊出$S$元
(前後順序不同視為一樣)

這時候你會發現原來的一維DP不太好去定義
這時候就可以用到剛剛提到的增維
多增加一維來表示最後可挑選硬幣的狀態
定義$dp[i][j]$為前$i$個硬幣，總和為$j$元的方法數
而每次我們都去考慮他上一個可挑選硬幣($i-1$)枚的數字

再把以上答案加總即是子問題答案
轉移式:$dp[i][j+a[i]]+=dp[i-1][j]$

時間複雜度:$O(NS)$

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,s;
    cin>>n>>s;
    vector <int> a(105);
    vector <vector <int> >  dp(1005,vector <int>(1005));
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){//將0元初始化為1種可能
        dp[i][0]=1;
    }
    dp[0][a[0]]=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<=s;j++){
            if(j+a[i]<=s){//需在範圍內轉移
                dp[i][j+a[i]]+=dp[i-1][j];
            }
        }
    }
    cout<<dp[n-1][s]<<"\n";
    return 0;
}

有沒有辦法用更小的空間呢

可以發現，每次轉移$i$時只跟$i-1$有關
所以其實根本不需要到$NS$的空間
每次都只需將原本存$i$的位置去往右平移該陣列

但如果單存往右轉移會發生捨麼事
例如說:假設硬幣為$2$元，因此會先在$dp[0]$的時候更新$dp[2]$，而到$dp[2]$的時候又會更新$dp[4]$，但$dp[2]$已經有考慮過$2$元了，不應再考慮一次

所以我們可以試著倒著去遍歷(第2個for迴圈)
如此一來就不會因為前面的狀態轉移去影響後面的轉移

我們把上述做法稱為空間優化

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,s;
    cin>>n>>s;
    int a[105],dp[1005]={0};
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    dp[0]=1;
    for(int j=0;j<n;j++){
        for(int i=s;i>=0;i--){//由大到小轉移
            if(i+a[j]<=s){//需在範圍內轉移
                dp[i+a[j]]+=dp[i];
            }
        }
    }
    cout<<dp[s]<<"\n";
return 0;
}

---

<!-- 換零錢問題$-3$

今天有大小為N的A序列，每個數字代表的是硬幣面額，最少需要幾枚硬幣可湊出S元
之前我們有在greedy做過一樣的題目，但只有在特定的面額才會正確
如s=8,a={1,4,5}
如果你先貪心的拿了最高硬幣5元，這樣總需4枚硬幣，但如果拿2枚4元硬幣，反而總硬幣數還比較少。-->
## 區間dp

> 給你一串長度為$n$的數列，你可以對他做以下操作：
選擇連續的三個數，刪除中間的數
>
> 只是每次操作都會造成負擔，負擔的量為三數的乘積
如何在最少的負擔下使得數列剩下兩數

作法：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int a[105] , dp[105][105];
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ;++j)
            dp[i][j] = 10000;
    for(int i = 1 ; i < n ; i++)
         dp[i][i+1] = 0;
    int ans = INT_MAX;
    for(int i = 1 ; i <= n ; i++)
        for(int j = i - 1 ; j >= 1 ; j--)
            for(int k = j + 1 ; k <= i - 1 ; k++){
                dp[j][i] = min(dp[j][k] + dp[k][i] + a[j]*a[k]*a[i] , dp[j][i]);
            }
    cout << dp[1][n] << "\n";
    return 0;
}

## 經典問題

1.背包問題

(1)0/1背包問題
> 給你$n$種物品，每種物品都會有它的價值$v_i$和他的重量$w_i$，你有一個背包，總共可以放入總重為$W$的物品，每一種物品只可以放1個，請求出能夠放入最高價值是多少。($1\leq W\leq1000$ , $1\leq n\leq100$)

這個問題如果用greedy先放價值最高的物品，很容易就可以找出錯誤的例子，因此要使用dp來從所有情況中找出最好的。

我們以$dp[i][j]$表示只看前$i$個物品，且剛好取重量為$j$的最大價值。
則$dp[i][j]=\left\{
\begin{aligned}
dp[i-1][j]\quad \quad \quad \quad \small{(不取第i個物品的情況)}\\
dp[i-1][j-w[i]] + v[i] \quad\small{(取了第i個物品的情況)}
\end{aligned}
\right.$

#include<bits/stdc++.h>
using namespace std;

int main(){
    int v[105], w[105], dp[105][1005] = {0};
    int n, W;
    cin >> n >> W;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){
            dp[i][j] = dp[i-1][j]; // 不取的情況
        }
        for(int j = w[i]; j <= W; j++){
            dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j]); // 取的情況
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << "\n";
    return 0;
}

<a></a>
:::spoiler 小測驗
以下是一個爛掉的code，請問它的bug在哪裡？

#include<bits/stdc++.h>
using namespace std;

int main(){
    int v[105],w[105], dp[105][1005];
    int n,W;
    cin >> n >> W;
    for(int i = 1 ; i <= n ; i++)
        cin >> v[i] >> w[i];
    for(int i = 1 ; i <= W ; i++)
        dp[0][i] = -10000;
    dp[0][0] = 0;
    int ans = 0;
    for(int i = 1 ; i <= n; i++){
        for(int j = w[i] ; j <= W ; ++j){
            dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j]));//轉移狀態
            ans = max(ans , dp[i][j]);
        }
    }
    cout << ans << "\n";
    return 0;
}

:::
<a></a>
::: spoiler 提示1
以下的測資可以讓這個code WA

3 3
1 1
10 2
100 2

:::
::: spoiler 解答
觀察程式碼的轉移式，可以發現它的轉移式只有
$dp[i][j]=dp[i-1][j-w[i]] + v[i]$
<a></a>
也就是說這個code無法處理跳過某一項不取的情況！
:::
<a></a>
當然我們也可以空間壓縮，而且寫法更簡潔

#include<bits/stdc++.h>
using namespace std;

int main(){
    int v[105], w[105], dp[1005] = {0};
    int n, W;
    cin >> n >> W;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = W; j >= w[i]; j--){ // 這邊倒過來跑很重要
            dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
            ans = max(ans, dp[j]);
        }
    }
    cout << ans << "\n";
    return 0;
}

(2)無限背包問題

> 給你$n$種物品，每種物品都會有它的價值$val_i$和他的重量$w_i$，你有一個背包，總共可以放入總重為$W$的物品，每一種物品可以放很多個，請求出能夠放入最高價值是多少。($1\leq W\leq 1000$ , $1\leq n\leq 1000$)

作法和0/1背包差不多

#include<bits/stdc++.h>
using namespace std;

int main(){
    int v[105], w[105], dp[1005] = {0};
    int n, W;
    cin >> n >> W;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = w[i]; j >= W; j--){ // 這邊不用倒過來跑
            dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
            ans = max(ans , dp[j]);
        }
    }
    cout << ans << "\n";
    return 0;
}