動態規劃（Dynamic Programming），簡稱DP，透過把原問題分解為相對簡單的子問題來求解，並且把已經算過的數字存起來，之後再碰到就可以直接用。

解題方法

• 問題拆解，找到問題之間的關聯
• 定義DP狀態
• 列出轉移式
• 初始化邊界條件

Zerojudge - 東東爬階梯

給定一個整數\(0<n<100\)，假設階梯有\(n\)階，每次可以走一階或兩階，求有幾種走法

• 走到第\(i\)階可以由第\(i-1\)階走\(1\)階，也可以由第\(i-2\)階走\(2\)階
• 令\(dp[i]\)為走\(i\)階的方法數
• \(dp[i]=dp[i-1]+dp[i-2]\)
• \(dp[0]=dp[1]=1\)
• \(ans=dp[n]\)

程式碼：

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

int dp[100];

signed main()
{
    int i,n;
    dp[0]=dp[1]=1;
    for(i=2;i<100;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    while(cin >> n)
    {
        cout << dp[n] << "\n";
    }
}

CSES - Dice Combinations

給定一個整數\(1\le n\le 10^{6}\)，可以骰六面骰子任意次數，求有多少種方法使得點數總和是\(n\)，順序交換算不同次

• 總和為\(i\)可以由原本總和\(i-1\)骰到\(1\)，由原本總和\(i-2\)骰到\(2\)，依此類推
• 令\(dp[i]\)為總和\(i\)點的方法數
• \(dp[i]=\sum_{k=1}^{6}dp[i-k],i-k\ge 0\)
• \(dp[0]=1\)
• \(ans=dp[n]\)

程式碼：

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
 
int dp[1000001];

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

CSES - Dice Probability

給定整數\(1\le n\le 100\)，\(1\le a,b\le 6n\)，骰六面骰子\(n\)次，求點數總和介於\(a\)和\(b\)之間的機率

• 總和為\(i\)可以由原本總和\(i-1\)骰到\(1\)，其中骰到1的機率為\(\frac{1}{6}\)，依此類推
• 令\(dp[i][j]\)為骰了\(i\)次，總和\(j\)點的機率
• \(dp[i][j]=\frac{1}{6}\sum_{k=1}^{6}dp[i-1][j-k],j-k\ge 0\)
• \(dp[0][0]=1\)
• \(ans=\sum_{k=a}^{b}dp[n][k]\)

程式碼：

#include <bits/stdc++.h>
using namespace std;
 
double dp[101][601];
 
int main()
{
    int n,a,b,i,j,k;
    double ans=0;
    cin >> n >> a >> b;
    dp[0][0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=i*6;j++)
        {
            for(k=max(0,j-6);k<=j-1;k++)
                dp[i][j]+=dp[i-1][k];
            dp[i][j]/=6;
        }
    }
    for(;a<=b;a++)
    {
        ans+=dp[n][a];
    }
    cout << fixed << setprecision(6) << ans << "\n";
}

CSES - Static Range Sum Queries

給定一長度為\(n\)的陣列\(x_1,x_2,\dots,x_n\)，並有\(q\)次詢問，每次詢問求陣列\([a,b]\)範圍內的和，\(1\le n,q\le2\cdot 10^5\)

• 一維前綴和

• 令\(dp[i]\)為前\(i\)項的前綴和
• \(dp[i]=dp[i-1]+x_i\)
• \(dp[0]=0\)
• \(ans=dp[b]-dp[a-1]\)

程式碼：

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int dp[200001];
 
signed main()
{
    int n,q,x,i,a,b;
    cin >> n >> q;
    for(i=1;i<=n;i++)
    {
        cin >> x;
        dp[i]=dp[i-1]+x;
    }
    while(q--)
    {
        cin >> a >> b;
        cout << dp[b]-dp[a-1] << "\n";
    }
}

CSES - Forest Queries

給定一\(n\times n\)的二維陣列，每個位置是\(0\)或\(1\)，並有\(q\)次詢問，每次詢問求陣列\((y_1,x_1)\sim(y_2,x_2)\)範圍內的和，\(1\le n\le1000,1\le q\le2\cdot 10^5\)

• 二維前綴和

• 令\(dp[i][j]\)為\((1,1)\sim(i,j)\)範圍內的和
• \(dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+c_{i,j}\)
• \(dp[0][0]=dp[0][1]=\dots=dp[0][n]=0\)
• \(dp[0]dp[0]=dp[1][0]=\dots=dp[n][0]=0\)
• \(ans=dp[y_2][x_2]-dp[y2][x1-1]-dp[y1-1][x2]+dp[y1-1][x1-1]\)

預處理：

詢問：

程式碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int dp[1001][1001];
 
signed main()
{
    int n,q,i,j,y1,x1,y2,x2;
    char c;
    cin >> n >> q;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin >> c;
            if(c=='*')
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+1;
            else
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
        }
    }
    while(q--)
    {
        cin >> y1 >> x1 >> y2 >> x2;
        cout << dp[y2][x2]-dp[y2][x1-1]-dp[y1-1][x2]+dp[y1-1][x1-1] << "\n";
    }
}

CSES - Maximum Subarray Sum

給定一個長度為\(n\)的陣列\(x_1,x_2,\dots,x_n\)，\(1\le n\le 2\cdot 10^5\)，求最大連續非空子陣列和

• 要有至少一個元素
• 令\(dp[i]\)為前\(i\)項的最大連續非空子陣列和
• \(dp[i]=max(dp[i-1]+x_i,x_i)\)
• \(dp[0]=0\)
• \(ans=max(dp[1],dp[2],\dots,dp[n])\)

程式碼：

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

int dp[200001];

signed main()
{
    int n,x,ans=LONG_LONG_MIN,i;
    cin >> n;
    for(i=0;i<n;i++)
    {
        cin >> x;
        dp[i]=max(dp[i-1]+x,x);
        ans=max(ans,dp[i]);
    }
    cout << ans << "\n";
}

ZeroJudge - 投資遊戲

給定一個長度為\(n\)的陣列\(x_1,x_2,\dots,x_n\)，\(1\le n\le 150000\)，求最大連續子陣列和，其中可以跳過\(k\)個數字，\(k\le 20\)

• 可以不包含任何元素
• 令\(dp[i][j]\)為跳過\(i\)個數字，前\(j\)項的最大連續子陣列和
• \(dp[0][0]=dp[1][0]=\dots=dp[k][0]=0\)
• \(dp[0][j]=max(dp[j-1]+x_j,0)\)
• \(dp[i][j]=max(dp[i-1][j-1],dp[i][j-1]+x_j)\)
• \(ans=max(dp[k][1],dp[k][2],\dots,dp[k][n])\)

程式碼：

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

int x[150001],dp[21][150001];

signed main()
{
    int n,k,i,j;
    cin >> n >> k;
    for(j=1;j<=n;j++)
    {
        cin >> x[j];
        dp[0][j]=max(dp[0][j-1]+x[j],0ll);
    }
    for(i=1;i<=k;i++)
    {
        for(j=1;j<=n;j++)
        {
            dp[i][j]=max(dp[i-1][j-1],dp[i][j-1]+x[j]);
        }
    }
    cout << *max_element(dp[k]+1,dp[k]+n+1) << "\n";
}

AtCoder - Knapsack 1

有\(N\)種物品，每種物品有重量\(w\)與價值\(v\)
每個物品最多可以選一次，求選的物品重量不超過\(W\)的情況，價值總和最大是多少

• \(0/1\)背包問題，代表選或不選

• 令\(dp[i][j]\)為選前\(i\)個物品且重量\(\le j\)的最大價值
• \(dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_i]+v_i)\)
• \(dp[0][0]=dp[0][1]=\dots=dp[0][W]=0\)
• \(ans=dp[N][W]\)

程式碼：

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

int dp[101][100001];

signed main()
{
    int N,W,w,v,i,j;
    cin >> N >> W;
    for(i=1;i<=N;i++)
    {
        cin >> w >> v;
        for(j=0;j<=W;j++)
        {
            dp[i][j]=max(dp[i-1][j],j-w>=0?dp[i-1][j-w]+v:0);
        }
    }
    cout << dp[N][W] << "\n";
}

Luogu - 宝物筛选

有\(n\)種物品，每種物品有重量\(w\)、價值\(v\)與數量\(m\)
每個物品最多可以選\(m\)次，求選的物品重量不超過\(W\)的情況，價值總和最大是多少

• 有限背包問題，每種物品有數量限制

• 把每一種物品拆成\(m\)個物品，用\(0/1\)背包解
• TLE

• 令\(m=2^{p}-1+k\)，其中\(k\)滿足\(k\le2^{p}-1\)，則物品可分成\(2^{0},2^{1},\dots,2^{p-1},k\)個
• 以上的數字可以湊出所有\(\le m\)的任何數字
• 每個數字為一堆，當成一個物品，用\(0/1\)背包解

• 證明：
• 1. 假設所需的數字\(\le 2^{p}-1\)，則這個數字可以表示為二進制的\(p\)位數字，考慮每一位可以是\(0\)或\(1\)，這個數字有\(2^p\)種排列方式，又數字最小值為每位都是\(0\) \(=0\)，最大值為每位都是\(1\) \(=2^0\times\frac{2^p-1}{2-1}=2^p-1\)，因此這\(2^p\)個數剛好對應到\(0\sim2^p-1\)
• 2. 假設所需的數\(>2^{p}-1\)，且最大值為\(m\)，這個數字\(\le2^{p}-1+k\)，由1.可知\(2^{p}-1\)內的數字都可以湊出來，因此\(\ge k\)且\(\le2^{p}-1+k\)的數字也可以湊出來，又\(k\le2^{p}-1\)，因此\(> 2^{p}-1\)且\(\le2^{p}-1+k\)的數字都可以被湊出來

程式碼：

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

int dp[40001];

signed main()
{
    int n,W,v,w,m,i,j,tmp;
    cin >> n >> W;
    for(i=1;i<=n;i++)
    {
        cin >> v >> w >> m;
        for(tmp=1;tmp<=m;tmp*=2)
        {
            m-=tmp;
            for(j=W;j>=tmp*w;j--)
            {
                dp[j]=max(dp[j],dp[j-tmp*w]+tmp*v);
            }
        }
        if(m)
        {
            for(j=W;j>=m*w;j--)
            {
                dp[j]=max(dp[j],dp[j-m*w]+m*v);
            }
        }
    }
    cout << dp[W] << "\n";
}

Luogu - 疯狂的采药

有\(m\)種草藥，每種草藥有採收需要時間\(a\)與價值\(b\)
每種草藥可以無限制地採，求採收時間不超過\(t\)的情況，價值總和最大是多少

• 無限背包問題，物品沒有數量限制

• 令\(dp[i]\)為總時間\(\le i\)的最大價值
• \(dp[i]=max(dp[i],dp[i-a_j]+b_j)\)
• \(dp[0]=0\)
• \(ans=dp[t]\)
• 因為在任何時間都可以選任何草藥，所以每種草藥可以取無限次

程式碼：

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

int a[10001],b[10001],dp[10000001];

signed main()
{
    int t,m,i,j;
    cin >> t >> m;
    for(i=1;i<=m;i++)
        cin >> a[i] >> b[i];
    for(i=1;i<=t;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[j]<=i)
                dp[i]=max(dp[i],dp[i-a[j]]+b[j]);
        }
    }
    cout << dp[t] << "\n";
}

CSES - Minimizing Coins

給定\(n\)枚硬幣，價值\(c_1,c_2,\dots,c_n\)元，求最少要用幾個硬幣才能湊出\(x\)元，\(1\le n\le 100,1\le x\le 10^6\)

• 令\(dp[j]\)為湊出\(j\)元所需的最少硬幣數
• \(dp[j]=min(dp[j],dp[j-c_i]+1)\)
• \(dp[0]=0\)
• 先假設\(dp[1]=dp[2]=\dots=dp[x]=INF\)
• \(ans=dp[x],dp[x]\not =INF\)
• \(ans\)無解\(,dp[x]=INF\)

程式碼：

#include <bits/stdc++.h>
#define INF 0x3F3F3F3F
using namespace std;

int dp[1000001];
 
int main()
{
    memset(dp,0x3F,sizeof(dp));
    dp[0]=0;
    int n,x,c,i,j;
    cin >> n >> x;
    for(i=1;i<=n;i++)
    {
        cin >> c;
        for(j=c;j<=x;j++)
        {
            if(dp[j-c]!=INF)
                dp[j]=min(dp[j],dp[j-c]+1);
        }
    }
    if(dp[x]!=INF)
        cout << dp[x] << "\n";
    else
        cout << -1 << "\n";
}

CSES - Coin Combinations I

給定\(n\)枚硬幣，價值\(c_1,c_2,\dots,c_n\)元，求湊出\(x\)元的方法數，不同順序算不同種，\(1\le n\le 100,1\le x\le 10^6\)

• 令\(dp[i]\)為湊出\(i\)元的方法數
• \(dp[i]=dp[i]+dp[i-c_j]\)
• \(dp[0]=1\)
• \(ans=dp[x]\)
• 在每個價錢都跑一次所有硬幣，所以不同順序也會被算進去

程式碼：

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
 
int c[101],dp[1000001];
 
signed main()
{
    int n,x,i,j;
    cin >> n >> x;
    for(i=1;i<=n;i++)
        cin >> c[i];
    dp[0]=1;
    for(i=1;i<=x;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i-c[j]>=0)
                dp[i]=(dp[i]+dp[i-c[j]])%MOD;
        }
    }
    cout << dp[x] << "\n";
}

CSES - Coin Combinations II

給定\(n\)枚硬幣，價值\(c_1,c_2,\dots,c_n\)元，求湊出\(x\)元的方法數，不同順序算同一種，\(1\le n\le 100,1\le x\le 10^6\)

• 令\(dp[j]\)為湊出\(j\)元的方法數
• \(dp[j]=dp[j]+dp[j-c_j]\)
• \(dp[0]=1\)
• \(ans=dp[x]\)
• 每個硬幣依序跑一次所有價錢，因此必定照著題目給的順序，同一種組合只會有一種排列

程式碼：

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
 
int dp[1000001];

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