一、學習目標

• 會把問題抽象成：狀態、轉移、初始值、答案位置、迭代順序（五步驟）。
• 熟悉一維 DP 的兩大類：
  • 計數型（有幾種方法）：例 Dice、Climbing Stairs。
  • 最優化（最少/最大）：例 Removing Digits、House Robber。
• 能寫出迭代式（bottom-up）程式，避免遞迴爆棧；懂得做空間優化（滾動變數）。

二、觀念說明

為什麼要 DP？（什麼題適合 DP）

• 重疊子問題：不同做法會不斷遇到相同子問題（例如湊和為 i 的方法數，很多路徑都會問到）。
• 最優子結構：最終答案可由子問題的最佳答案組合而成（例如最少步數、最大收益）。
• 枚舉爆炸：暴力樹狀搜索呈指數級，DP 把「狀態」壓縮到多項式級計算。
  一句話：把「大問題」拆成「一群彼此重疊的小問題」，每個只解一次並記錄。

五步驟模板（務必內化）

1. 狀態 State：定義 dp[...] 代表什麼「子問題」。

• 例（Dice）：dp[i] = 用 1..6 的點數和成 i 的方法數。
• 例（Removing Digits）：dp[i] = 把 i 變成 0 的最少步數。

2. 轉移 Transition：從更小的子問題推到現在這個子問題。

• Dice：dp[i] = Σ dp[i-k]（k=1..6 且 i-k≥0）。
• Removing Digits：列舉 i 的每個非零位數 d：dp[i] = 1 + min(dp[i-d])。

3. 初值 Base：邊界條件。

• Dice：dp[0]=1（和為 0 的方法只有「不取」）。
• Removing Digits：dp[0]=0（0 已是目標，不需步數）；其餘先設成大數（INF）。

4. 答案位置 Answer：通常是 dp[n]，或 min/max(dp[*])。

兩題都是 dp[n]。

5. 迭代順序 Order：確保當你在算 dp[i] 時，所需的更小狀態已經計好。

• Dice/Removing Digits 都是 i 由小到大。
• 背包會有特別的順序（0/1 背包倒序、完全背包正序）

初值怎麼想？（常錯點）

• 計數型：通常 dp[0]=1，代表「空選擇」也是一種方式。很多人寫成 0 導致整條鏈都是 0。
• 最優化型：dp[0]=0 很常見；其他未知狀態先設 INF，避免被誤選進最優解。
• 合法性：若某狀態不可達，保持 INF（或未訪標記）就好，不要硬轉移。

DP 的幾個思維模式（看到題目時如何判斷）

• 序列型：dp[i] 代表前 i 個（或和為 i），決策多是「取/不取、選哪個步幅/面值」。
• 區間型：dp[l][r]，常見在括號匹配、合併石子、矩陣連乘（Day 18）。
• 狀態壓縮：用 bitmask 表子集合，dp[mask][last]（Day 19）。
• 路徑型：網格路徑、DAG 上的 DP（拓撲序 + DP）。
• 背包家族：容量維度 + 物品迭代（Day 16）。

三、CSES實戰演練

題目1:Dice Combinations（計數 DP）

原題:
https://cses.fi/problemset/task/1633

題意:
給 n（1 ≤ n ≤ 10^6）。用 1~6 的骰子和成 n，有多少種方式？對 1e9+7 取模。

解題思路:

• 狀態：dp[i] = 和為 i 的方法數。
• 轉移：dp[i] = sum(dp[i-k])，k=1..6 且 i-k≥0。
• 初始：dp[0]=1（空取法）。
• 迭代：i 由小到大。

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

int main(){
    int n;
    cin>>n;
    vector<int> dp(n+1,0);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=6;j++){
            if(i-j>=0){
                dp[i]=(dp[i]+dp[i-j])%MOD;
            }
        }
    }
    cout<<dp[n]<<"\n";
    return 0;
}

題目2:Removing Digits（最少步數 DP）

原題:
https://cses.fi/problemset/task/1637

題意:
給 n（1 ≤ n ≤ 10^6）。每一步可把 n 減去它十進位表示中的一個非零數字。問把 n 變成 0 的最少步數。

解題思路:

• 狀態：dp[i] = 把 i 變成 0 的最少步數。
• 轉移：列舉 i 的每個非零位數 d，dp[i] = 1 + min(dp[i - d])。
• 初始：dp[0] = 0；其餘先設大數。
• 迭代：i = 1..n，每次抽取位數。

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

void digits(int x, vector<int>& buf) {
    buf.clear();
    while (x > 0) {
        int d = x%10;
        if (d != 0) buf.push_back(d);
        x /= 10;
    }
}

int main() {
    int n; 
    cin >> n;
    const int INF = 1e9;
    vector<int> dp(n+1, INF);
    dp[0] = 0;

    vector<int> buf;
    for (int i=1; i<=n; i++) {
        digits(i, buf);
        int best = INF;
        for (int t=0; t<buf.size(); t++) {
            int d = buf[t];
            if (i-d >= 0) {
                int cand = dp[i-d] + 1;
                if (cand<best) best=cand;
            }
        }
        dp[i] = best;
    }
    cout << dp[n] << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Climbing Stairs（斐波那契型，一維 DP/滾動）

原題:
https://leetcode.com/problems/climbing-stairs/description/

題意:
每步可走 1 或 2 階，爬到第 n 階有幾種走法？

解題思路:
f[n] = f[n-1] + f[n-2]，f[0]=1，f[1]=1。

class Solution {
public:
    int climbStairs(int n) {
        long long a = 1, b = 1; // f[0], f[1]
        for (int i = 2; i <= n; i++) {
            long long c = a+b; // f[i]
            a = b; 
            b = c;
        }
        return b;
    }
};

題目2:House Robber（鄰接不可同搶）

原題:
https://leetcode.com/problems/house-robber/description/

題意:
nums[i] 為每棟房子的金額；不能搶相鄰兩棟。求最大收益。

解題思路:

• 狀態：dp[i] = 考慮前 i 棟（索引 0..i-1）能搶到的最大值。
• 轉移：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。
• 初始：dp[0]=0, dp[1]=nums[0]。
• 空間優化：用兩個變數 prev2, prev1 代表 dp[i-2], dp[i-1]。

class Solution {
public:
    int rob(vector<int>& nums) {
        long long prev2 = 0;  // dp[0]
        long long prev1 = nums.empty() ? 0 : nums[0]; // dp[1]
        for (int i = 2; i <= nums.size(); i++) {
            long long take = prev2 + nums[i-1];
            long long skip = prev1;
            long long cur = (take > skip) ? take : skip;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};