一、學習目標

• 把不同型態的 DP（計數型、最佳化型、線性 DP、環狀 DP、字串 DP）串起來。
• 熟練「狀態定義 → 轉移 → 初始條件 → 答案位置」的完整流程。
• 實作滾動陣列、模數運算與邊界處理，確保可在賽場上快速上手。

二、DP觀念總結

• 狀態與答案對齊：確定 dp[i] / dp[i][x] 的語意，最後要哪個格子。
• 轉移的依賴方向：確保迴圈順序正確（例如 0/1 背包需倒序，線性/鄰近轉移按 i 往前）。
• 滾動陣列：當 dp[i] 只依賴 dp[i-1] 時，用兩排/一排節省記憶體。
• 模數：常見 MOD = 1e9+7；加法後 %=MOD、減法後補 +MOD。
• 拆解複雜題：找出子問題的「最小跨步」（例如鄰值 ±1、子集合補集、線段不交疊、環斷開為線）。

三、CSES實戰演練

題目1：Two Sets II（等和分組計數，1…n 兩集合）

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

題意：
將 {1..n} 分成兩組，兩組元素和相等，問共有幾種分法（順序與組內排列不計，取模 1e9+7）。

解題思路：
總和 S=n(n+1)/2，若為奇數則 0；否則計算「子集合和為 S/2」的種數。
注意：每個劃分會被「子集合 vs 補集」算到兩次 → 最終答案需 除以 2（用模逆元）。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;
int addmod(int a,int b){ a+=b; if(a>=MOD) a-=MOD; return a; }

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    long long S = 1LL*n*(n+1)/2;
    if(S & 1LL){ cout<<0<<"\n"; return 0; }
    int T = (int)(S/2);

    vector<int> dp(T+1, 0);
    dp[0] = 1;
    for(int x=1; x<=n; ++x){
        for(int s=T; s>=x; --s){
            dp[s] = addmod(dp[s], dp[s-x]);
        }
    }
    // 除以 2（模逆元 2^{-1} = (MOD+1)/2）
    long long inv2 = (MOD + 1LL)/2;
    cout << (long long)dp[T] * inv2 % MOD << "\n";
    return 0;
}

題目2：Array Description（相鄰差 ≤ 1 的填數計數）

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

題意：
長度 n 的陣列，值域 1..m。給定部分位置（0 代表可自由指定），要求相鄰元素差的絕對值 ≤ 1，問有幾種填法（取模）。

解題思路:
狀態：dp[x] = 目前位置 i，且 a[i]=x 的方法數
轉移：newdp[x] = dp[x-1] + dp[x] + dp[x+1]（留意邊界 1、m）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; if(!(cin>>n>>m)) return 0;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];

    vector<int> dp(m+1, 0), ndp(m+1, 0);
    if(a[0]==0){
        for(int x=1;x<=m;x++) dp[x]=1;
    }else{
        dp[a[0]] = 1;
    }

    for(int i=1;i<n;i++){
        fill(ndp.begin(), ndp.end(), 0);
        if(a[i]==0){
            for(int x=1;x<=m;x++){
                long long v = dp[x];
                if(x>1) v += dp[x-1];
                if(x<m) v += dp[x+1];
                ndp[x] = (int)(v % MOD);
            }
        }else{
            int x = a[i];
            long long v = dp[x];
            if(x>1) v += dp[x-1];
            if(x<m) v += dp[x+1];
            ndp[x] = (int)(v % MOD);
        }
        dp.swap(ndp);
    }
    long long ans = 0;
    for(int x=1;x<=m;x++) ans = (ans + dp[x]) % MOD;
    cout << ans << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1：213. House Robber II

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

重點：首尾相鄰 → 不能同時取 0 與 n-1。
做法：答案 = max(rob(linear, 0..n-2), rob(linear, 1..n-1))；線性版即經典 198 題：dp[i]=max(dp[i-1], dp[i-2]+val)。

class Solution {
    int robLinear(const vector<int>& a, int l, int r){
        int pre2 = 0, pre1 = 0; // dp[i-2], dp[i-1]
        for(int i=l;i<=r;i++){
            int cur = max(pre1, pre2 + a[i]);
            pre2 = pre1; pre1 = cur;
        }
        return pre1;
    }
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        return max(robLinear(nums, 0, n-2), robLinear(nums, 1, n-1));
    }
};

題目2：139. Word Break（字串切詞 DP）

原題:
https://leetcode.com/problems/word-break/

題意：
判斷字串能否被詞典完整切分。

狀態：
dp[i]=s[0..i) 可切分；轉移：存在 j<i 且 dp[j]==true 且 s[j..i) 在字典中 → dp[i]=true。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        int n = s.size(), maxL = 0;
        for (auto &w: wordDict) maxL = max(maxL, (int)w.size());
        vector<char> dp(n+1, 0);
        dp[0] = 1;
        for(int i=1;i<=n;i++){
            for(int len=1; len<=maxL && len<=i; ++len){
                if(!dp[i-len]) continue;
                if(st.count(s.substr(i-len, len))){ dp[i]=1; break; }
            }
        }
        return dp[n];
    }
};