[TOC]

# [Dice Combinations](https://cses.fi/problemset/task/1633)
:::spoiler 解法:
令$dp[i]$為$n=i$時的答案(特別定義$dp[0]$=1)，考慮每一種組合方法的最後一個數字，例如$dp[x]$中最後一個數字為$4$的組合方法數恰為$dp[x-4]$種，則:
$$
dp[i]=\sum_{j=\max (0,i-6)}^{i-1} dp[j]
$$
複雜度$\text{O} (n)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,mod=1e9+7;
    cin>>n;
    vector<int> dp(n+1);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=max(0,i-6);j<=i-1;j++){
            dp[i]+=dp[j];
            dp[i]%=mod;
        }
    }
    cout<<dp[n]<<endl;
}

:::
# [Minimizing Coins](https://cses.fi/problemset/task/1634)
:::spoiler 解法:
定義$dp[i]$為$x=i$時的答案，集合$S$為硬幣的面額，窮舉最後一枚硬幣的面額，則:
$$
dp[i]=\mathop{\min}_{j\in S,i-j\geq 0} (dp[i-j]+1)
$$
複雜度$\text{O} (nx)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    vector<int> S(n),dp(x+1,1e7);
    dp[0]=0;
    for(int i=0;i<n;i++){
        cin>>S[i];
    }
    for(int i=1;i<=x;i++){
        for(int j:S){
            if(i-j<0) continue;
            dp[i]=min(dp[i],dp[i-j]+1);
        }
    }
    if(dp[x]==1e7) cout<<-1<<endl;
    else cout<<dp[x]<<endl;
    return 0;
}

:::
# [Coin Combinations I](https://cses.fi/problemset/task/1635)
:::spoiler 解法:
令$dp[i]$為$n=i$時的答案(特別定義$dp[0]$=1)，且集合$S$為硬幣的面額，考慮每一種組合方法的最後一個數字，例如$dp[x]$中最後一個數字為$4$的組合方法數恰為$dp[x-4]$種，則:
$$
dp[i]=\sum_{j\in S,i-j\geq 0} dp[i-j]
$$
複雜度$\text{O} (nx)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x,mod=1e9+7;
    cin>>n>>x;
    vector<int> S(n),dp(x+1);
    dp[0]=1;
    for(int i=0;i<n;i++){
        cin>>S[i];
    }
    for(int i=1;i<=x;i++){
        for(int j:S){
            if(i-j<0) continue;
            dp[i]+=dp[i-j];
            dp[i]%=mod;
        }
    }
    cout<<dp[x]<<endl;
    return 0;
}

:::
# [Coin Combinations II](https://cses.fi/problemset/task/1636)
:::spoiler 解法:
令$dp[i][j]$為只使用前$j$種數字，組合出$i$的方法數。先枚舉$j$，注意到新加入的數字可能用很多次，不過只要由小到大枚舉$i$，就可以包含到所有情形。以範測為例，$dp[(6+3)]$能從$dp[6]$轉移，而因為先枚舉$6$才枚舉$10$，所以已經有包含到(3+3)的情況了。如果不太能理解可以試著開二維的dp陣列或者直接看code。

複雜度$\text{O}(nx)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x,mod=1e9+7;
    cin>>n>>x;
    vector<int> S(n),dp(x+1);
    for(int i=0;i<n;i++){
        cin>>S[i];
    }
    dp[0]=1;
    for(int j:S){
        for(int i=j;i<=x;i++){
            dp[i]+=dp[i-j];
            dp[i]%=mod;
        }
    }
    cout<<dp[x]<<endl;
}

:::
# [Removing Digits](https://cses.fi/problemset/task/1637)
:::spoiler 解法:
令$dp[i]$為$n=i$時的答案，集合$S_i$為$i$各位數的數字。則:
$$
dp[i]=\mathop{min}_{j\in S_i} (dp[i-j]+1)
$$
複雜度$\text{O}(n\log_{10} n)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> dp(n+1,1e6+1);
    queue<int> q;
    for(int i=1;i<n+1;i++){
        int temp=i;
        while(temp){
            if(temp%10!=0) q.push(temp%10);
            temp/=10;
        }while(q.size()!=0){
            dp[i]=min(dp[i],dp[i-q.front()]+1);
            q.pop();
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

:::
# [Grid Paths](https://cses.fi/problemset/task/1638/)
:::spoiler 解法:
$$
dp[i][j]=dp[i-1][j]+dp[i][j-1]
$$
複雜度$\text{O}(n^2)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,mod=1e9+7;
    cin>>n;
    vector<vector<int>> v(n,vector<int>(n)),dp(n,vector<int>(n));
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<n;j++){
            if(s[j]=='.') v[i][j]=1;
            else v[i][j]=0;
        }
    }
    dp[0][0]=v[0][0];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(v[i][j]){
                if(i>0) dp[i][j]+=dp[i-1][j];
                if(j>0) dp[i][j]+=dp[i][j-1];
                dp[i][j]%=mod;
            }
        }
    }
    cout<<dp[n-1][n-1]<<endl;
    return 0;
}

:::
# [Book Shop](https://cses.fi/problemset/task/1158/)
:::spoiler 解法:
經典背包問題。
令$dp[i][j]$為只拿前$i$項物品，預算為$j$時可獲得的最大頁數，則有以下兩種情況:
對於第$i$個物品

不拿:
$$
dp[i][j]=dp[i-1][j]
$$
拿:
$$
dp[i][j]=dp[i-1][j-w[i]]+v[i]
$$
其中$w$為重量(價格)，$v$為價值(頁數)

對兩種情況取$\max$

複雜度$\text{O}(nx)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    vector<int> price(n),pages(n);
    for(int i=0;i<n;i++) cin>>price[i];
    for(int i=0;i<n;i++) cin>>pages[i];
    vector<vector<int>> dp(n+1,vector<int>(x+1));
    for(int i=1;i<n+1;i++){
        for(int j=1;j<x+1;j++){
            if(j>=price[i-1]){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-price[i-1]]+pages[i-1]);
            }
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][x]<<endl;
    return 0;
}

:::
# [Array Description](https://cses.fi/problemset/task/1746)
:::spoiler 解法:
其實和[Grid Paths](https://hackmd.io/apWfaWY0T1i47d0xhGHYNw?both#Grid-Paths)非常像，只不過轉移點變為三個，另外需要注意不要超出邊界。

複雜度$\text{O}(nm)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    ll n,m,mod=1e9+7;
    cin>>n>>m;
    vector<vector<int>> dp(n,vector<ll>(m+1));
    vector<int> v(n);
    for(ll i=0;i<n;i++){
        cin>>v[i];
    }
    if(v[0]>0) dp[0][v[0]]=1;
    else{
        for(ll i=1;i<=m;i++){
            dp[0][i]=1;
        }
    }
    for(int i=1;i<n;i++){
        if(v[i]>0){
            dp[i][v[i]]=dp[i-1][v[i]-1]+dp[i-1][v[i]];
            if (v[i]<m) dp[i][v[i]]+=dp[i-1][v[i]+1];
        }else{
            for(int j=1;j<=m;j++){
                if(j<m){
                    dp[i][j+1]+=dp[i-1][j];
                }
                if(j>1){
                    dp[i][j-1]+=dp[i-1][j];
                }
                dp[i][j]+=dp[i-1][j];
                dp[i][j]%=mod;
            }
        }
    }
    int ans=0;
    for(ll i=0;i<=m;i++){
        ans+=dp[n-1][i];
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

:::
# [Counting Towers](https://cses.fi/problemset/task/2413)
:::spoiler 解法:
一樣先從狀態和轉移去想，狀態顯而易見的，就是令$dp[i]$為$n=i$時的答案，那麼轉移呢?
轉移就是找$dp[i]$和$dp[i-1]$、$dp[i-2]$、$dp[i-3]$……有什麼關係。

因此試著從$2*i$的圖形中找$2*(i-1)$，發現似乎大部分都可以由$2*(i-1)$的圖形以某種方式**長**出來，因此或許可以藉由觀察最下方兩排來得出一些轉移方式，但似乎沒有一個較不失一般性的描述。於是嘗試**分情形討論**:
我們從左上開始編號1~8

發現1、2、4上半部的情形是相同的，3、5、6、7、8的上半部也是相同的，因此總共就是$3*(dp[i-1]中最底層沒有豎的情形)+5*(dp[i-1]中最底層有豎的情形)$，但是因為下一層($dp[i+1]$)也會用到，因此分開紀錄。

令$dp[0][i]$為$n=i$時，最底層沒有豎的情形;
令$dp[1][i]$為$n=i$時，最底層有豎的情形。
則:
$$
dp[0][i]=2\times dp[0][i-1]+dp[1][i-1]\\
dp[1][i]=dp[0][i-1]+4\times dp[1][i-1]
$$

複雜度$\text{O}(n)$

:::

:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int mod=1e9+7;
    vector<vector<ll>> dp(2,vector<ll>(2e6));
    dp[0][1]=1;
    dp[1][1]=1;
    for(int i=2;i<2e6;i++){
        dp[0][i]=dp[0][i-1]*2+dp[1][i-1];
        dp[1][i]=dp[1][i-1]*4+dp[0][i-1];
        dp[0][i]%=mod;
        dp[1][i]%=mod;
    }
    int t;
    cin>>t;
    while(t--){
        int a;
        cin>>a;
        cout<<(dp[0][a]+dp[1][a])%mod<<endl;
    }
    return 0;
}

:::
:::spoiler 延伸:
[I. 鐵路鋪設 (rail)](https://tioj.ck.tp.edu.tw/problems/2259)
這題需要使用矩陣快速冪來加速，不過可以先試著找找看遞迴式。
:::
# [Edit Distance](https://cses.fi/problemset/task/1639)
:::spoiler 解法:
定義$dp[i][j]$為第一個字串前$i$(1-based)個字元和第二個字串前$j$(1-based)個字元的最小edit distance。

接下來以範測觀察如何轉移，從$dp[4][5]$來看，很明顯因為最後一個字元相同，所以$dp[4][5]=dp[3][4]$。如果不同，如$dp[3][4]$，考慮所有可能的最後的操作，若是加字(刪字的操作可以都由加字來代替，因此不考慮)，則轉移點是$dp[2][4]$或$dp[3][3]$，若為改字，則轉移點為$dp[2][3]$。因此:

若$s_1[i]=s_2[j]$，
$$
dp[i][j]=dp[i-1][j-1]
$$

若$s_1[i]\neq s_2[j]$，
$$
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
$$

複雜度$\text{O}(nm)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    int n=a.size(),m=b.size();
    vector<vector<int>> dp(n+1,vector<ll>(m+1));
    for(ll i=0;i<m+1;i++){
        dp[0][i]=i;
    }for(ll i=0;i<n+1;i++){
        dp[i][0]=i;
    }
    for(ll i=1;i<n+1;i++){
        for(ll j=1;j<m+1;j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

:::
# [Rectangle Cutting](https://cses.fi/problemset/task/1744)
:::spoiler 解法:
令$dp[i][j]$為$a=i$且$b=j$時的答案。
觀察到任意尺寸的矩形(正方形除外)的最佳分割方式一定有一刀是會將矩形一分為二的(證明:Trivial!)，因此枚舉此線所有可能的切割位置，最後再取最小值。即若$i\neq j$，則:

$$
\begin{aligned}
dp[i][j]=\min(&\mathop{\min}_{0<k<i} dp[k][j]+dp[i-k][j]+1,
\\ &\mathop{\min}_{0<k<j} dp[i][k]+dp[i][j-k]+1)
\end{aligned}
$$

複雜度$\text{O}((\max(a,b))^3)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<vector<int>> dp(501,vector<int> (501,1e9));
    for(int i=1;i<501;i++){
        for(int j=1;j<501;j++){
            if(i==j){
                dp[i][j]=0;
                continue;
            }
            for(int k=1;k<j;k++){
                dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[i][k]+1);
            }
            for(int k=1;k<i;k++){
                dp[i][j]=min(dp[i][j],dp[i-k][j]+dp[k][j]+1);
            }
        }
    }
    int a,b;
    cin>>a>>b;
    cout<<dp[a][b]<<endl;
    return 0;
}

:::
# [Money Sums](https://cses.fi/problemset/task/1745)
:::spoiler 解法:
其實和[Coin Combinations II](https://hackmd.io/apWfaWY0T1i47d0xhGHYNw?view#Coin-Combinations-II)幾乎一模一樣，只不過每個硬幣都只能用一次，要解決也非常簡單，只要在遍歷dp陣列時**由後往前**就可以避免重複使用的問題(因為每一個轉移點都是上一輪留下來的)，如果不太能理解可以試著開二維的dp陣列或者直接看code。

複雜度$\text{O}(n^2\max (x))$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ans=0;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<bool> dp(1e5+1);
    dp[0]=1;
    for(int i:v){
        for(int j=1e5;j>=i;j--){
            if(dp[j-i]==1&&dp[j]==0){
                ans++;
                dp[j]=1;
            }
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=1e5;i++){
        if(dp[i]) cout<<i<<" ";
    }
    cout<<endl;
}

:::
# [Removal Game](https://cses.fi/problemset/task/1097)
:::spoiler 解法:
令$dp[i][j]$為陣列剩下$[i,j]$時，先手能得到的最大分數。
每一個dp值的轉移點一定是長度紹一的陣列而來。因此從$j-i=0$的情況開始觀察如何計算。

若$j-i=0$，$dp[i][j]=v[i]$
若$j-i=1$，
$$
\begin{aligned}
dp[i][j]&=\max (v[i],v[j])
\\ &=\max (v[i]+v[j]-dp[i+1][j],v[i]+v[j]-dp[i][j-1])
\\ &=v[i]+v[j]-\min(dp[i+1][j],dp[i][j-1])
\end{aligned}
$$
若$j-i=2$，
$$
dp[i][j]=v[i]+v[i+1]+v[j]-\min(dp[i+1][j],dp[i][j-1])
$$

不難觀察到:
$$
dp[i][j]=\sum_{k=i}^{j} v[k]-\min(dp[i+1][j],dp[i][j-1])
$$
換句話說，從$[i,j]$頭或尾拿走一張就會剩下$[i+1,j]$或$[i,j-1]$而對手也會拿最好的(也就是$dp[i+1][j]$或$dp[i][j-1]$)，而這區間拿到的就是(區間總和)-(對手拿走的)。
區間總和可以簡單的利用前綴和計算。

複雜度$\text{O}(n^2)$
:::
:::spoiler code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<ll> pre(n+1);
    vector<vector<ll>> dp(n,vector<ll>(n));
    for(int i=0;i<n;i++){
        cin>>pre[i+1];
        pre[i+1]+=pre[i];
    }
    for(int k=0;k<n;k++){
        for(int i=0;i+k<n;i++){
            int j=i+k;
            if(k==0){
                dp[i][j]=pre[i+1]-pre[i];
                continue;
            }
            dp[i][j]=pre[j+1]-pre[i]-min(dp[i+1][j],dp[i][j-1]);
        }
    }
    cout<<dp[0][n-1]<<endl;
    return 0;
}

:::
# [Two Sets II](https://cses.fi/problemset/task/1093/)
先備知識:模逆元
:::spoiler 解法:
換個角度思考:在$[1,n]$的數字中，有多少種組合使得總合為$\frac{n(n+1)}{4}$(即$\frac{\sum_{i=1}^{n}i\;}{2}$)，沒錯! 就是[Money Sums](https://hackmd.io/apWfaWY0T1i47d0xhGHYNw?view#Money-Sums)!
最後要注意，答案要除以二(因為要分兩邊)，但是遇到取模，所以就要使用模逆元。

複雜度$\text{O}(n^3)$
:::
:::spoiler code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n,mod=1e9+7;
    cin>>n;
    ll tar=n*(n+1)/2;
    if(tar%2==1){
        cout<<0<<endl;
        return 0;
    }
    vector<ll> dp(2e5);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=2e5;j>=i;j--){
            dp[j]+=dp[j-i];
            dp[j]%=mod;
        }
    }
    cout<<dp[tar/2]*500000004%mod<<endl; 
    return 0;
}

:::
# [Increasing Subsequence](https://cses.fi/problemset/task/1145/)
先備知識:二分搜
:::spoiler 解法:
**$\text{O}(n^2)$作法:**
令$dp[i]$為以$i$結尾的LIS長度，則:
$$
dp[i]=\mathop{\max}_{j<i, v[j]<v[i]} dp[j]+1
$$

---
**$\text{O}(n\log n)$作法:**

觀察平方做法後發現，有一些位置不會用到:
若$dp[a]=dp[b]$，且$a<b$，則$v[a]\geq v[b]$(因為若$v[a]<v[b]$，表示$b$可以接在$a$後面，則$dp[a]=dp[b]$不成立)，且對於所有$i>b$，可以接在$b$後的不一定可以接在$a$後，因此$a$就可以不用考慮了。

整理一下:若$dp[a]=dp[b]$，且$a<b$，則$a$可以不用考慮。
也就是說對於相同的dp值，我們只要維護**位置最後面**的就好了。

所以我們需要改一下dp的定義:
令$dp[i]$為長度為$i$的嚴格遞增序列的結尾中位置最後方的數字。

由左到右遍歷，根據定義，所有數字在遍歷到時都會被加入到dp序列(因為所有數字都會是當前的數字中位置最後面的)，問題是要加入到哪一個dp值。要讓LIS越長越好，所以要加入到dp序列中最後一個比自己小的數字後方，並且由上方的觀察發現，dp序列會嚴格遞增，也就是說，要將每個數字加入到dp序列中的`lower_bound`。
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ans=0;
    cin>>n;
    vector<int> dp={0};
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(dp.back()<a){
            dp.push_back(a);
            ans++;
        }
        dp[lower_bound(dp.begin(),dp.end(),a)-dp.begin()]=a;
    }
    cout<<ans<<endl;
    return 0;
}

:::
# [Projects](https://cses.fi/problemset/task/1140/)
先備知識:排序、二分搜、離散化
:::spoiler 開始之前
先去寫[Movie Festival](https://cses.fi/problemset/task/1629/)，這題是所有價值皆相等的特殊情形。
:::
:::spoiler 解法:
寫過上面那一題應該知道要照結束時間排序了，不再贅述。

定義$dp[i]$為在$i$這個時間點能得到的最大價值，則:

若有一場電影$[a,i]$，價值$w$，則:
$$
dp[i]=max(dp[i-1],dp[a-1]+w)
$$

若無，則
$$
dp[i]=dp[i-1]
$$
:::
:::spoiler code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>> pro(n,vector<int>(3));
    vector<int> num;
    for(int i=0;i<n;i++){
        cin>>pro[i][0]>>pro[i][1]>>pro[i][2];
        num.push_back(pro[i][0]);
        num.push_back(pro[i][1]);
    }
    sort(num.begin(),num.end());
    num.resize(unique(num.begin(),num.end())-num.begin());
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            pro[i][j]=lower_bound(num.begin(),num.end(),pro[i][j])-num.begin();
        }
    }
    sort(pro.begin(),pro.end(),[](auto i,auto j){
        return i[1]<j[1];
    });
    vector<ll> dp(4e5+1);
    ll ans=0,pos=1;
    for(auto i:pro){
        while(pos<i[1]+1){
            dp[pos]=max(dp[pos],dp[pos-1]);
            pos++;
        }
        dp[pos]=max(dp[pos],dp[i[0]]+i[2]);
        ans=max(ans,dp[pos]);
    }
    cout<<ans<<endl;
    return 0;
}

:::
# [Elevator Rides](https://cses.fi/problemset/task/1653)
先備知識:位元運算
:::spoiler 解法:
請參考[位元dp](https://hackmd.io/hTQrRJDaQ2C2X9UouWengw?view#%E4%BD%8D%E5%85%83dp)
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<int> dp(1<<n),last(1<<n);
    dp[0]=1;
    last[0]=0;
    for(int i=1;i<=1<<n;i++){//窮舉子集合
        dp[i]=INT_MAX;
        last[i]=INT_MAX;
        for(int j=0;j<n;j++){//窮舉轉移點
            if(i&(1<<j)){
                int a=i-(1<<j);//轉移點
                if(last[a]+v[j]<=x){
                    if(dp[a]<dp[i]||(dp[a]==dp[i]&&last[a]+v[j]<last[i])){
                        dp[i]=dp[a];
                        last[i]=last[a]+v[j];
                    }
                }else {
                    if(dp[a]+1<dp[i]||(dp[a]+1==dp[i]&&v[j]<last[i])){
                        dp[i]=dp[a]+1;
                        last[i]=v[j];
                    }
                }

            }
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
    return 0;
}

:::
:::spoiler 延伸:
[Hamiltonian Flights](https://cses.fi/problemset/task/1690)
[Team Building](https://codeforces.com/contest/1316/problem/E)
[Matching](https://atcoder.jp/contests/dp/tasks/dp_o?lang=en)
[貨郎問題](https://judge.tcirc.tw/ShowProblem?problemid=d089)
:::
# [Counting Tilings](https://cses.fi/problemset/task/2181)
先備知識:二元運算
:::spoiler 解法:
這題不能用和[Rectangle Cutting](https://hackmd.io/apWfaWY0T1i47d0xhGHYNw?view#Rectangle-Cutting)一樣的解法，因為存在以下構造方式:

定義$dp[i][j][S]$為前$i-2$行以及第$i-1$行的前$j$行皆填滿，且輪廓(即圖中膚色的地方)填充狀態為集合$S$的方法數。以下圖為例，即為$dp[2][3][0110010]$(皆為0-based)

(注:$\oplus$為$\text{XOR}$)

* 若(i,j)有放:
* 若為橫放: $dp[i][j][S]=dp[i][j-1][S\oplus 2^i]$
* 若為直放(條件:$(i-1,j)$為空): $dp[i][j][S]=dp[i][j-1][S\oplus 2^{i-1}]$
* 若(i,j)沒放: $dp[i][j][S]=dp[i][j-1][S\oplus 2^i]$

另外需特別考慮$i=0$的情況，由於情況和上方類似(僅不包含放直的情況)，故在此省略。

複雜度$\text{O}(nm2^n)$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,mod=1e9+7;
    cin>>n>>m;
    vector<vector<vector<int>>> dp(n,vector<vector<int>>(m,vector<int> (1<<n)));
    dp[0][0][(1<<n)-2]=1;
    for(int j=0;j<m;j++){
        for(int i=0;i<n;i++){
            for(int s=0;s<1<<n;s++){
                if(i==0){
                    if(j>0) dp[i][j][s]=dp[n-1][j-1][s^1];
                }
                else{
                    if(s&(1<<i)){
                        dp[i][j][s]=dp[i-1][j][s^(1<<i)];
                        if(s&(1<<(i-1))){
                            dp[i][j][s]+=dp[i-1][j][s^(1<<(i-1))];
                        }
                    }
                    else{
                        dp[i][j][s]=dp[i-1][j][s^(1<<i)];
                    }
                }
                dp[i][j][s]%=mod;
            }
        }
    }
    cout<<dp[n-1][m-1][(1<<n)-1]<<endl;
    return 0;
}

:::
:::spoiler 參考資料:
[USACO GUIDE](https://usaco.guide/adv/dp-more?lang=cpp#code)有一個將空間壓縮到一維($\text{O}(2^n)$)的寫法。
:::
# [Counting Numbers](https://cses.fi/problemset/task/2220)
:::spoiler 解法:
令$dp[i][j]$ 為 $[j\times 10^{i},(j+1)\times 10^{i})$ 中的答案(也就是所有$j$開頭的$i+1$位數的答案)，則:
$$
dp[i][j]=\sum_{0\leq k<10,k\neq j \vee j=0} dp[i-1][k]
$$

稍微觀察，或者print出來時就會發現$dp[i][1]$到$dp[i][9]$都一樣

那麼就非常簡單了!
以$321$為例:拆成$[0,300)$、$[300,320)$、$[320,322)$三個部分做計算。

但是在實作上，有不少地方要注意，例如:$[300,320)$其實是$(dp[1][0]-dp[0][0])+dp[1][1]$，因為$300$不合法；另外，若前綴已經不合法了，那麼剩下的位數也都不用算了。

複雜度$\text{O}(\log_{10}(\max(a,b)))$
:::
:::spoiler code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    vector<vector<ll>> dp(20,vector<ll>(10));
    for(int i=0;i<10;i++){
        dp[0][i]=1;
    }
    for(int i=1;i<20;i++){
        for(int j=0;j<10;j++){
            for(int k=0;k<10;k++){
                if(j==0 || j!=k) dp[i][j]+=dp[i-1][k];
                if(j!=0 && i>1 && k==0) dp[i][j]-=dp[i-2][k];
            }
        }
    }
    ll a,b,ans1=0,ans2=0;
    vector<int> v1,v2;
    cin>>a>>b;
    b++;
    while(a){
        v1.push_back(a%10);
        a/=10;
    }
    while(b){
        v2.push_back(b%10);
        b/=10;
    }
    for(int i=v1.size()-1;i>=0;i--){
        for(int j=0;j<v1[i];j++){
            if(i!=v1.size()-1 && v1[i]>0 && i>0) ans1+=dp[i][0]-dp[i-1][0];
            else ans1+=dp[i][j];
        }
        if(i!=v1.size()-1 && v1[i]>v1[i+1]) ans1-=dp[i][v1[i+1]];
        if(v1[i]==v1[i+1]) break;
    }
    for(int i=v2.size()-1;i>=0;i--){
        for(int j=0;j<v2[i];j++){
            if(i!=v2.size()-1 && v2[i]>0 && i>0) ans2+=dp[i][0]-dp[i-1][0];
            else ans2+=dp[i][j];
        }
        if(i!=v2.size()-1 && v2[i]>v2[i+1]) ans2-=dp[i][v2[i+1]];
        if(v2[i]==v2[i+1]) break;
    }
    cout<<ans2-ans1<<endl;
}

:::