動態規劃

01背包

有 $n$ 件物品和一個容量為 $W$ 的背包，第 $i$ 件物品的體積為 $w[i]$，價值為 $v[i]$，求解將哪些物品裝入背包中使總價值最大。

思路：

我們設$dp[i][j]$表示前$i$件物品放入一個容量為$j$的背包可以獲得的最大價值

如果不放第$i$件物品，那么問題就變成了前$i?1$件物品放入一個容量為$j$的背包可以獲得的最大價值即$dp[i?1][j]$

如果放第$i$件物品，那么問題變成了前$i?1$件物品放入一個容量為$j?w[i]$的背包可以獲得的最大價值,即當前可以獲得最大價值為

前$i?1$件物品放入一個容量為$j?w[i]$的背包加上當前第$i$件物品放入背包的價值，即$dp[i?1][j?w[i]]+v[i]$

于是我們可以得到 轉移方程 $dp[i][j]=max(dp[i?1][j],dp[i?1][j?w[i]]+v[i])$。

for (int i = 1; i <= n; i++)for (int j = 0; j <= W; j++){dp[i][j] = dp[i - 1][j]; // 不選第 i 個物品if (j >= w[i]) // 如果當前容量 j 能裝下物品 idp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); // 不選第i個物品和選了第i個物品取最大值}

我們可以發現，第 $i$ 個物品的狀態是由第 $i?1$ 個物品轉移過來的，每次的 $j$ 轉移過來后，第 $i?1$ 個方程的 $j$ 已經沒用了，于是我們想到可以把二維方程壓縮成 一維 的，用以 優化空間復雜度。

for (int i = 1; i <= n; i++)  //當前裝第 i 件物品for (int j = W; j >= w[i]; j--)  //背包容量為 jdp[j] = max(dp[j], dp[j - w[i]] + v[i]);  //判斷背包容量為 j 的情況下能是實現總價值最大是多少

完全背包

有 $n$ 件物品和一個容量為 $W$ 的背包，第 $i$ 件物品的體積為 $w[i]$，價值為 $v[i]$，每件物品有無限個，求解將哪些物品裝入背包中使總價值最大。

思路:

思路和01背包差不多，但是每一件物品有無限個，其實就是從每 種 物品中取 $0, 1, 2,… $ 件物品加入背包中

for (int i = 1; i <= n; i++)for (int j = 0; j <= W; j++)for (int k = 0; k * w[i] <= j; k++)    //選取幾個物品 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);

實際上，我們可以發現，取 $k$ 件物品可以從取 $k?1$ 件轉移過來，那么我們就可以將 $k$ 的循環優化掉

for (int i = 1; i <= n; i++)for (int j = 0; j <= W; j++){dp[i][j] = dp[i - 1][j];if (j >= w[i])dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);}

和 01 背包 類似地壓縮成一維

for (int i = 1; i <= n; i++)for (int j = w[i]; j <= W; j++)dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

多重背包

有 $n$ 種物品和一個容量為 $W$ 的背包，第 $i$ 種物品的體積為 $w[i]$，價值為 $v[i]$，數量為 $s[i]$，求解將哪些物品裝入背包中使總價值最大。

思路：

對于每一種物品，都有 $s[i]$ 種取法，我們可以將其轉化為01背包問題

for (int i = 1; i <= n; i++){for (int j = W; j >= 0; j--)for (int k = 0; k <= s[i]; k++){if (j - k * w[i] < 0) break;dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);}

上述方法的時間復雜度為 $O(n?m?s)$。

for (int i = 1; i <= n; i++){scanf("%lld%lld%lld", &x, &y, &s);  //x 為體積， y 為價值， s 為數量t = 1;while (s >= t){w[++num] = x * t;v[num] = y * t;s -= t;t *= 2;}w[++num] = x * s;v[num] = y * s;
}
for (int i = 1; i <= num; i++)for (int j = W; j >= w[i]; j--)dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

盡管采用了 二進制優化，時間復雜度還是太高，采用 單調隊列優化，將時間復雜度優化至 $O(n?m)$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, W, w, v, s, f[N], g[N], q[N];
int main(){ios::sync_with_stdio(false);cin.tie(0);cin >> n >> W;for (int i = 0; i < n; i ++ ){memcpy ( g, f, sizeof f);cin >> w >> v >> s;for (int j = 0; j < w; j ++ ){int head = 0, tail = -1;for (int k = j; k <= W; k += w){if ( head <= tail && k - s * w > q[head] ) head ++ ;//保證隊列長度 <= s while ( head <= tail && g[q[tail]] - (q[tail] - j) / w * v <= g[k] - (k - j) / w * v ) tail -- ;//保證隊列單調遞減 q[ ++ tail] = k;f[k] = g[q[head]] + (k - q[head]) / w * v;}}}cout << f[W] << "\n";return 0;
}

混合背包

放入背包的物品可能只有 1 件（01背包），也可能有無限件（完全背包），也可能只有可數的幾件（多重背包）。

思路：

分類討論即可，哪一類就用哪種方法去 $dp$。

#include <bits/stdc++.h>using namespace std;int n, W, w, v, s;int main(){cin >> n >> W;vector <int> f(W + 1);for (int i = 0; i < n; i ++ ){cin >> w >> v >> s;if (s == -1){for (int j = W; j >= w; j -- )f[j] = max(f[j], f[j - w] + v);}else if (s == 0){for (int j = w; j <= W; j ++ )f[j] = max(f[j], f[j - w] + v);}else {int t = 1, cnt = 0;vector <int> x(s + 1), y(s + 1);while (s >= t){x[++cnt] = w * t;y[cnt] = v * t;s -= t;t *= 2;}x[++cnt] = w * s;y[cnt] = v * s;for (int i = 1; i <= cnt; i ++ )for (int j = W; j >= x[i]; j -- )f[j] = max(f[j], f[j - x[i]] + y[i]);}}cout << f[W] << "\n";return 0;
}

二維費用的背包

有 $n$ 件物品和一個容量為 $W$ 的背包，背包能承受的最大重量為 $M$，每件物品只能用一次，第 $i$ 件物品的體積是 $w[i]$，重量為 $m[i]$，價值為 $v[i]$，求解將哪些物品放入背包中使總體積不超過背包容量，總重量不超過背包最大容量，且總價值最大。

思路：

背包的限制條件由一個變成兩個，那么我們的循環再多一維即可。

for (int i = 1; i <= n; i++)for (int j = W; j >= w; j--)  //容量限制for (int k = M; k >= m; k--)  //重量限制dp[j][k] = max(dp[j][k], dp[j - w][k - m] + v);

分組背包

有 $n$ 組物品，一個容量為 $W$ 的背包，每組物品有若干，同一組的物品最多選一個，第 $i$ 組第 $j$ 件物品的體積為 $w[i][j]$，價值為 $v[i][j]$，求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且使總價值最大。

思路：

考慮每組中的某件物品選不選，可以選的話，去下一組選下一個，否則在這組繼續尋找可以選的物品，當這組遍歷完后，去下一組尋找。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, W, s[N], w[N][N], v[N][N], dp[N];
int main(){cin >> n >> W;for (int i = 1; i <= n; i++){scanf("%d", &s[i]);for (int j = 1; j <= s[i]; j++)scanf("%d %d", &w[i][j], &v[i][j]);}for (int i = 1; i <= n; i++)for (int j = W; j >= 0; j--)for (int k = 1; k <= s[i]; k++)if (j - w[i][k] >= 0)dp[j] = max(dp[j], dp[j - w[i][k]] + v[i][k]);cout << dp[W] << "\n";return 0;
}

有依賴的背包

有 $n$ 個物品和一個容量為 $W$ 的背包，物品之間有依賴關系，且之間的依賴關系組成一顆 樹 的形狀，如果選擇一個物品，則必須選擇它的 父節點，第 $i$ 件物品的體積是 $w[i]$，價值為 $v[i]$，依賴的父節點的編號為 $p[i]$，若 $p[i]$ 等于 -1，則為 根節點。求將哪些物品裝入背包中，使總體積不超過總容量，且總價值最大。

思路：

定義 $f[i][j]$ 為以第 $i$ 個節點為根，容量為 $j$ 的背包的最大價值。那么結果就是 $f[root][W]$，為了知道根節點的最大價值，得通過其子節點來更新。所以采用遞歸的方式。
對于每一個點，先將這個節點裝入背包，然后找到剩余容量可以實現的最大價值，最后更新父節點的最大價值即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, W, w[N], v[N], p, f[N][N], root;
vector <int> g[N];
void dfs(int u){for (int i = w[u]; i <= W; i ++ )f[u][i] = v[u];for (auto v : g[u]){dfs(v);for (int j = W; j >= w[u]; j -- )for (int k = 0; k <= j - w[u]; k ++ )f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);}
}
int main(){cin >> n >> W;for (int i = 1; i <= n; i ++ ){cin >> w[i] >> v[i] >> p;if (p == -1) root = i;else g[p].push_back(i);}dfs(root);cout << f[root][W] << "\n";return 0;
}

背包問題求方案數

有 $n$ 件物品和一個容量為 $W$ 的背包，每件物品只能用一次，第 $i$ 件物品的重量為 $w[i]$，價值為 $v[i]$，求解將哪些物品放入背包使總重量不超過背包容量，且總價值最大，輸出 最優選法的方案數，答案可能很大，輸出答案模 $10^9+7$ 的結果。

思路：

開一個儲存方案數的數組 $cnt$，$cnt[i]$ 表示容量為 $i$ 時的 方案數，先將 $cnt$ 的每一個值都初始化為 1，因為 不裝任何東西就是一種方案，如果裝入這件物品使總的價值 更大，那么裝入后的方案數 等于 裝之前的方案數，如果裝入后總價值 相等，那么方案數就是 二者之和

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e9 + 7, N = 1010;
LL n, W, cnt[N], f[N], w, v;
int main(){cin >> n >> W;for (int i = 0; i <= W; i ++ )cnt[i] = 1;for (int i = 0; i < n; i ++ ){cin >> w >> v;for (int j = W; j >= w; j -- )if (f[j] < f[j - w] + v){f[j] = f[j - w] + v;cnt[j] = cnt[j - w];}else if (f[j] == f[j - w] + v){cnt[j] = (cnt[j] + cnt[j - w]) % mod;}}cout << cnt[W] << "\n";return 0;
}

背包問題求具體方案

signed main() {int Task = 1;for (cin >> Task; Task; Task--) {int n, m;cin >> n >> m;vector<int> w(n + 1), v(n + 1);vector<vector<int>> dp(n + 2, vector<int>(m + 2));for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}for (int i = n; i >= 1; i--) {for (int j = 0; j <= m; j++) {dp[i][j] = dp[i + 1][j];if (j >= w[i]) {dp[i][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);}}}vector<int> ans;for (int i = 1; i <= n; i++) {if (m - w[i] >= 0 && dp[i][m] == dp[i + 1][m - w[i]] + v[i]) {ans.push_back(i);// cout << i << " ";m -= w[i];}}cout << ans.size() << "\n";for (auto i : ans) {cout << i << " ";}cout << "\n";}
}

數位 DP

/* pos 表示當前枚舉到第幾位
sum 表示 d 出現的次數
limit 為 1 表示枚舉的數字有限制
zero 為 1 表示有前導 0
d 表示要計算出現次數的數 */
const int N = 15;
LL dp[N][N];
int num[N];
LL dfs(int pos, LL sum, int limit, int zero, int d) {if (pos == 0) return sum;if (!limit && !zero && dp[pos][sum] != -1) return dp[pos][sum];LL ans = 0;int up = (limit ? num[pos] : 9);for (int i = 0; i <= up; i++) {ans += dfs(pos - 1, sum + ((!zero || i) && (i == d)), limit && (i == num[pos]),zero && (i == 0), d);}if (!limit && !zero) dp[pos][sum] = ans;return ans;
}
LL solve(LL x, int d) {memset(dp, -1, sizeof dp);int len = 0;while (x) {num[++len] = x % 10;x /= 10;}return dfs(len, 0, 1, 1, d);
}

狀壓 DP

**題意：**在 $n?n$ 的棋盤里面放 $k$ 個國王，使他們互不攻擊，共有多少種擺放方案。國王能攻擊到它上下左右，以及左上左下右上右下八個方向上附近的各一個格子，共8個格子。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 15, M = 150, K = 1500;
LL n, k;
LL cnt[K];    //每個狀態的二進制中 1 的數量
LL tot;    //合法狀態的數量
LL st[K];    //合法的狀態
LL dp[N][M][K];    //第 i 行，放置了 j 個國王，狀態為 k 的方案數
int main(){ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;for (int s = 0; s < (1 << n); s ++ ){  //找出合法狀態LL sum = 0, t = s;while(t){  //計算 1 的數量sum += (t & 1);t >>= 1;}cnt[s] = sum;if ( (( (s << 1) | (s >> 1) ) & s) == 0 ){  //判斷合法性st[ ++ tot] = s;}}dp[0][0][0] = 1;for (int i = 1; i <= n + 1; i ++ ){for (int j1 = 1; j1 <= tot; j1 ++ ){    //當前的狀態LL s1 = st[j1];for (int j2 = 1; j2 <= tot; j2 ++ ){    //上一行的狀態LL s2 = st[j2];if ( ( (s2 | (s2 << 1) | (s2 >> 1)) & s1 ) == 0 ){for (int j = 0; j <= k; j ++ ){if (j - cnt[s1] >= 0)dp[i][j][s1] += dp[i - 1][j - cnt[s1]][s2];}}}}}cout << dp[n + 1][k][0] << "\n";return 0;
}

常用例題

題意：在一篇文章（包含大小寫英文字母、數字、和空白字符（制表/空格/回車））中尋找 $\mathtt{helloworld}$（任意一個字母的大小寫都行）的子序列出現了多少次，輸出結果對 $10^9+7$ 的余數。

字符串 DP ，構建一個二維 DP 數組，$dp[i][j]$ 的 $i$ 表示文章中的第幾個字符，$j$ 表示尋找的字符串的第幾個字符，當字符串中的字符和文章中的字符相同時，即找到符合條件的字符， dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] ，因為字符串中的每個字符不會對后面的結果產生影響，所以 DP 方程可以優化成一維的， 由于字符串中有重復的字符，所以比較時應該從后往前。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e9 + 7;
char c, s[20] = "!helloworld";
LL dp[20];
int main(){dp[0] = 1;while ((c = getchar()) != EOF)for (int i = 10; i >= 1; i--)if (c == s[i] || c == s[i] - 32)dp[i] = (dp[i] + dp[i - 1]) % mod;cout << dp[10] << "\n";return 0;
}

---

題意：（最長括號匹配）給一個只包含‘(’，‘)’，‘[’，‘]’的非空字符串，“()”和“[]”是匹配的，尋找字符串中最長的括號匹配的子串，若有兩串長度相同，輸出靠前的一串。

設給定的字符串為 $\mathtt{s}$ ，可以定義數組 $dp[i],dp[i]$ 表示以 $s[i]$ 結尾的字符串里最長的括號匹配的字符。顯然，從 $i?dp[i]+1$ 到 $i$ 的字符串是括號匹配的，當找到一個字符是‘)’或‘]’時，再去判斷第 $i?1?dp[i?1]$ 的字符和第 $i$ 位的字符是否匹配，如果是，那么 dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]] 。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
string s;
int len, dp[maxn], ans, id;
int main(){cin >> s;len = s.length();for (int i = 1; i < len; i++){if ((s[i] == ')' && s[i - 1 - dp[i - 1]] == '(' ) || (s[i] == ']' && s[i - 1 - dp[i - 1]] == '[')){dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]];if (dp[i] > ans) {ans = dp[i];  //記錄長度id = i;  //記錄位置}}}for (int i = id - ans + 1; i <= id; i++)cout << s[i];cout << "\n";return 0;
}

---

題意：去掉區間內包含“4”和“62”的數字，輸出剩余的數字個數

int T,n,m,len,a[20];//a數組用于判斷每一位能取到的最大值
ll l,r,dp[20][15];
ll dfs(int pos,int pre,int limit){//記搜//pos搜到的位置，pre前一位數//limit判斷是否有最高位限制if(pos>len) return 1;//剪枝if(dp[pos][pre]!=-1 && !limit) return dp[pos][pre];//記錄當前值ll ret=0;//暫時記錄當前方案數int res=limit?a[len-pos+1]:9;//res當前位能取到的最大值for(int i=0;i<=res;i++)if(!(i==4 || (pre==6 && i==2)))ret+=dfs(pos+1,i,i==res&&limit);if(!limit) dp[pos][pre]=ret;//當前狀態方案數記錄return ret;
}
ll part(ll x){//把數按位拆分len=0;while(x) a[++len]=x%10,x/=10;memset(dp,-1,sizeof dp);//初始化-1（因為有可能某些情況下的方案數是0）return dfs(1,0,1);//進入記搜
}
int main(){cin>>n;while(n--){cin>>l>>r;if(l==0 && r==0)break;if(l) printf("%lld\n",part(r)-part(l-1));//[l,r](l!=0)else printf("%lld\n",part(r)-part(l));//從0開始要特判}
}