# 動態規劃
:::info
遞迴是由大到小，動態規劃是由小到大:把大問題拆成小問題，記住小問題的答案，組合成大問題答案
:::
> 動態規劃不是遞迴，不會要return自己。
> 動態規劃簡單說就是以空間複雜度為代價，換取時間複雜度的優化。

# 1D DP
DP的題目大多符合下列步驟
例: **爬樓梯問題**
> 有一棟樓梯有 n 階，每次你可以爬 1 階或 2 階，問你有幾種不同的爬法？
>
要素 | 說明 | 爬樓梯範例
| -------- | -------- | -------- |
1️⃣ 狀態定義 | 記錄「子問題」的解 | dp[i] = 爬到第 i 階的方法數
2️⃣ 狀態轉移方程 | 如何用小問題解大問題 | dp[i] = dp[i-1] + dp[i-2]
3️⃣ 初始狀態 | base case | dp[1] = 1, dp[2] = 2
4️⃣ 遍歷順序 | 從小到大累積結果 | for i in range(3, n+1)

## 外觀數列(費波納契數列)

ll fib(ll cnt){
    if (cnt == 0) return 0;
    vector<ll> li={1,1};
    for (ll i=2; i<=cnt; i++){
        li.push_back(li[i-1]+li[i-2]);
    }
    return li[cnt];
}

int main(){ io;
    ll a;
    while (cin >> a) {
        cout << fib(a) << endl;
    }
}

> 通常會建議用遞迴寫費波納契數列，網路上找的到很多範例，這裡就不特別做說明了

# 2D DP
考慮以下問題:
LCS(Longest Common Subsequence)最長共同子序列
[UVa - LCS](https://zerojudge.tw/ShowProblem?problemid=a133)
大家的想法通常會是:用雙重迴圈去跑，只要一A[i]與B[j]一樣就+1。
但如果今天題目輸入的兩個字串AB都超長，此時就會爆炸，這時不妨試一下DP的寫法!

DP LCS的想法是，我一直去比較1、2、3:怎樣才是最長序列(最優解)

# 滾動 DP
> DP 的技巧有許多種，通稱為 DP 優化，每種學問都很深，可以有效地減少時間複雜
度。我們先來看一種減少空間複雜度的技巧：滾動 DP。

**既然每次計算的時候只需要前兩項，那剩下那些用不到的就可以丟掉了。**

MOD = 10**9 + 7

def fibonacci(n):
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, (a + b) % MOD
    return b if n > 0 else 0

n = int(input())
print(fibonacci(n))

# 組合總和問題
## 演練 - 1
* 定義轉移: dp[i] = 骰出點數為 i 的組合數
* 定義完轉移式之後接下來就可以開始把公式推出來了
• 對於點數 i 來說，要使骰出的點數總和為 i ，會有 6 種可能
• 點數 i - 6 時再骰出 1 個 6 點
• 點數 i - 5 時再骰出 1 個 5 點
• 點數 i - 4 時再骰出 1 個 4 點
• and so on…
因此轉移式為 dp[i] = dp[i-1] + dp[i-2] + … + dp[i-6]
> 其實就是加法原理

### C++
domjudge python 一直超時idk why

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;

int main(){ io;
    ll i,j, n, MOD = pow(10,9)+7;
    cin >> n;
    ll dp[n+1] = {0};
    dp[0] = 1; // 直接丟骰子就可以實現

    for (i=1 ; i<n+1; i++){
        for (j=1 ; j<7; j++){
            if (i-j >= 0){
                dp[i] += dp[i-j];
                dp[i] %= MOD;
            }
        }
    }
    cout << dp[n];
}

過程演示

dp[0] = 1  # base
dp[1] = dp[0] = 1
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4
dp[4] = dp[3] + dp[2] + dp[1] + dp[0] = 4 + 2 + 1 + 1 = 8
dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0] = 8 + 4 + 2 + 1 + 1 = 16
dp[6] = dp[5] + dp[4] + dp[3] + dp[2] + dp[1] + dp[0] = 16 + 8 + 4 + 2 + 1 + 1 = 32
dp[7] = dp[6] + dp[5] + dp[4] + dp[3] + dp[2] + dp[1] = 32 + 16 + 8 + 4 + 2 + 1 = **63**

你會發現到DP[7]就不把dp[0]加進來了
:::warning
因為骰子沒辦法直接一丟就丟出7
:::
> dp[1] 是指全部1的情況:1+1+1+1+...

# 演練 - 2
一樣，用上面的動態規劃，加法原理求解就好

* 設 dp[i]為湊出金額 i 所需的最少硬幣數量。
* 初始化：dp[0] = 0（湊出金額 0，不用硬幣）

int main(){
    io;
    ll i,j, n, target;

    cin >> n >> target;
    vector<int> li(n);

    for (i=0;i<n;i++) cin >> li[i];
    
    ll INT = INT_MAX;
    vector<ll> dp(target+1, INT);
    dp[0] = 0; // 直接丟骰子就可以實現

    for (i=1 ; i<target+1; i++){
        for (auto j : li){
            if (i-j >= 0){
                dp[i] = min(dp[i-j]+1,dp[i]);
            }
        }
    }
    cout << dp[target];
}

以範例1做舉例:

> dp[11] = min(dp[11], dp[11 - 5] + 1)
> = min(dp[11], dp[6] + 1)

意思是：
:::warning
如果我知道湊出 6 元最少需要幾枚硬幣，那我只要再加上一枚 5 元硬幣，就可以湊出 11 元了！
:::

所以：

dp[6] = 2（例如可能是 1+5）

那 dp[11] = dp[6] + 1 = 3

也就是：加上這個 +1，代表你用了這個 coin！

## 進階 [LC39](https://hackmd.io/@QlAoGV8nSFyJy-hYETkq-g/Sy1HwzZhke/%2FuN65Ti31REesr868Sx9auw)
這題不是要問你有幾種組合，而是要你把所有組合都列出來
(當然，題目測資會比較小)

# DP - 枚舉
> 枚舉就是一種暴力解，但可以透過一些邊界，條件的判斷來**剪枝**

---

:::info
趁機宣傳一下我自己的個人網站跟Youtube頻道 !!

**[個人網站](https://hyc.eshachem.com/) | [Youtube頻道](https://www.youtube.com/@Hy.C)**
:::
@2025 Hy.C 陳毓
> Copyright ©Hy.C 陳毓 CC BY-NC-SA 4.0 | 禁止商業用途 | 轉載標記出處 | 改編作品必須在相同條款下分享。