分组背包、完全背包
分组背包：多个物品分组，每组只能取1件。每一组的物品都可能性展开就可以了。时间复杂度 O(物品数量 * 背包容量)
完全背包：与 01 背包的区别仅在于每种商品可以选取无限次。时间复杂度 O(物品数量 * 背包容量)
P1757 通天之分组背包
- 严格位置依赖的动态规划
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 时间复杂度 O(m * n)
int main() {// n 件物品，背包容量 mint m, n;cin >> m >> n;vector<vector<int>> arr(n + 1, vector<int>(3));for (int i = 1; i <= n; ++i)cin >> arr[i][0] >> arr[i][1] >> arr[i][2];// 根据组号排序sort(begin(arr), end(arr),[](vector<int> &v1, vector<int> &v2) {return v1[2] < v2[2];});// 组数int teams = 1;for (int i = 2; i <= n; ++i)if (arr[i][2] != arr[i - 1][2]) teams++;// dp[i][j] 表示从前面 i 个组中选取（每个组最多选一个），总重量不超过 j 时能获得的最大收益vector<vector<int>> dp(teams + 1, vector<int>(m + 1));// 首行为 0fill(begin(dp[0]), end(dp[0]), 0);for (int l = 1, r = 2, i = 1; l <= n; ++i) {// r 移动到下一组的开头while (r <= n && arr[l][2] == arr[r][2]) r++;// [l, r-1] 为当前组的物品for (int j = 0; j <= m; ++j) {// 一个都不选dp[i][j] = dp[i - 1][j];// 尝试选则组内的每一个for (int k = l; k < r; ++k)if (j - arr[k][0] >= 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[k][0]] + arr[k][1]);}// 处理下一组l = r++;}cout << dp[teams][m];
}
- 空间优化
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 时间复杂度 O(m * n)
int main() {// n 件物品，背包容量 mint m, n;cin >> m >> n;vector<vector<int>> arr(n + 1, vector<int>(3));for (int i = 1; i <= n; ++i)cin >> arr[i][0] >> arr[i][1] >> arr[i][2];// 根据组号排序sort(begin(arr), end(arr),[](vector<int> &v1, vector<int> &v2) {return v1[2] < v2[2];});// 组数int teams = 1;for (int i = 2; i <= n; ++i)if (arr[i][2] != arr[i - 1][2]) teams++;// dp[i][j] 表示从前面 i 个组中选取（每个组最多选一个），总重量不超过 j 时能获得的最大收益// 首行为 0vector<int> dp(m + 1, 0);for (int l = 1, r = 2, i = 1; l <= n; ++i) {// r 移动到下一组的开头，[l, r-1] 为当前组的物品while (r <= n && arr[l][2] == arr[r][2]) r++;// 从右往左for (int j = m; j >= 0; --j) {// 一个都不选，或者尝试选则组内的每一个for (int k = l; k < r; ++k)if (j - arr[k][0] >= 0)dp[j] = max(dp[j], dp[j - arr[k][0]] + arr[k][1]);}// 处理下一组l = r++;}cout << dp[m];
}
2218. 从栈中取出 K 个硬币的最大面值和
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:int maxValueOfCoins(vector<vector<int>> &piles, int m) {// 组数int n = piles.size();// dp[i][j] 表示前 i 组上，一共拿走 j 个硬币的情况下，获得的最大价值vector<vector<int>> dp(n + 1, vector<int>(m + 1));// 组号从 1 开始for (int i = 1; i <= n; ++i) {// 当前组vector<int> team = piles[i - 1];// 计算前缀和int t = min((int) team.size(), m);vector<int> preSum(t + 1);for (int j = 1; j <= t; ++j)preSum[j] = preSum[j - 1] + team[j - 1];// 更新动态规划表for (int j = 0; j <= m; ++j) {// 当前组一个硬币也不拿dp[i][j] = dp[i - 1][j];// i 组里拿走前 k 个硬币的方案for (int k = 1; k <= min(t, j); ++k)dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + preSum[k]);}}return dp[n][m];}
};
- 空间优化
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:int maxValueOfCoins(vector<vector<int>> &piles, int m) {// 组数int n = piles.size();// dp[i][j] 表示前 i 组上，一共拿走 j 个硬币的情况下，获得的最大价值// 首行全 0vector<int> dp(m + 1, 0);// 组号从 1 开始for (int i = 1; i <= n; ++i) {// 当前组vector<int> team = piles[i - 1];// 计算前缀和int t = min((int) team.size(), m);vector<int> preSum(t + 1);for (int j = 1; j <= t; ++j)preSum[j] = preSum[j - 1] + team[j - 1];// 更新动态规划表for (int j = m; j >= 0; j--) {// 当前组一个硬币也不拿// i 组里拿走前 k 个硬币的方案for (int k = 1; k <= min(t, j); ++k)dp[j] = max(dp[j], dp[j - k] + preSum[k]);}}return dp[m];}
};
P1616 疯狂的采药
完全背包(模版)
给定一个正数 t，表示背包的容量
有 m 种货物，每种货物可以选择任意个
每种货物都有体积 costs[i] 和价值 values[i]
返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
返回最大的价值
- 严格位置依赖的动态规划
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;#define ll long longint main() {int t, m;cin >> t >> m;vector<int> cost(m + 1);vector<int> value(m + 1);for (int i = 1; i <= m; ++i)cin >> cost[i] >> value[i];// dp[i][j] 表示前 i 号物品，每种可以无限拿，总代价不超过 j 的情况下，能获得的最大价值vector<vector<ll>> dp(m + 1, vector<ll>(t + 1));for (int i = 1; i <= m; ++i) {for (int j = 0; j <= t; ++j) {// 当前物品一个都不拿dp[i][j] = dp[i - 1][j];// 当前物品拿若干个if (j - cost[i] >= 0)dp[i][j] = max(dp[i][j], dp[i][j - cost[i]] + value[i]);}}cout << dp[m][t];
}
- 空间压缩
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;#define ll long longint main() {int t, m;cin >> t >> m;vector<int> cost(m + 1);vector<int> value(m + 1);for (int i = 1; i <= m; ++i)cin >> cost[i] >> value[i];// dp[i][j] 表示前 i 号物品，每种可以无限拿，总代价不超过 j 的情况下，能获得的最大价值// 首行全 0vector<ll> dp(t + 1, 0);for (int i = 1; i <= m; ++i) {// 从左往右for (int j = cost[i]; j <= t; ++j) {// 当前物品一个都不拿// 当前物品拿若干个dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);}}cout << dp[t] << endl;
}
10. 正则表达式匹配
- 暴力递归
#include <iostream>using namespace std;class Solution {
public:// s 从 i 下标开始能不能被 p 从 j 下标开始完全匹配出来bool recursive(string s, string p, int i, int j) {// 1. s 没后缀if (i == s.length()) {// 同时 p 也没后缀if (j == p.length()) return true;// p 还剩下一些后缀// 如果 p[j+1] 是 *，那么 p[j, j+1]可以消掉，然后看看再剩下的是不是都能消掉return j + 1 < p.length() && p[j + 1] == '*' && recursive(s, p, i, j + 2);}// 2. s 有后缀，p 没后缀if (j == p.length()) return false;// 3. 都有后缀// 3.1 j+1 位置不是 *if (j + 1 == p.length() || p[j + 1] != '*')return (s[i] == p[j] || p[j] == '.') && recursive(s, p, i + 1, j + 1);// 3.2 j+1 位置是 *// 完全背包// 选择1: 当前 p[j, j+1] 变成空，用 p 的 j+2 位置开始和 s 的 i 位置匹配bool p1 = recursive(s, p, i, j + 2);// 选择2: (s[i] == p[j] || p[j] == '.') 时，当前 p[j..j+1] 消去 s[i]bool p2 = (s[i] == p[j] || p[j] == '.') && recursive(s, p, i + 1, j);return p1 || p2;}bool isMatch(string s, string p) {return recursive(s, p, 0, 0);}
};
- 记忆化搜索
#include <iostream>
#include <vector>using namespace std;class Solution {
public:// s 从 i 下标开始能不能被 p 从 j 下标开始完全匹配出来bool recursive(string s, string p, int i, int j, vector<vector<int>> &dp) {if (dp[i][j] != 0) return dp[i][j] == 1;bool res;if (i == s.length()) {// 1. s 没后缀// 同时 p 也没后缀if (j == p.length()) {res = true;} else {// p 还剩下一些后缀// 如果 p[j+1] 是 *，那么 p[j, j+1]可以消掉，然后看看再剩下的是不是都能消掉res = j + 1 < p.length() && p[j + 1] == '*' && recursive(s, p, i, j + 2, dp);}} else if (j == p.length()) {// 2. s 有后缀，p 没后缀res = false;} else {if (j + 1 == p.length() || p[j + 1] != '*') {// 3. 都有后缀// 3.1 j+1 位置不是 *return (s[i] == p[j] || p[j] == '.') && recursive(s, p, i + 1, j + 1, dp);} else {// 3.2 j+1 位置是 *// 完全背包// 选择1: 当前 p[j, j+1] 变成空，用 p 的 j+2 位置开始和 s 的 i 位置匹配bool p1 = recursive(s, p, i, j + 2, dp);// 选择2: (s[i] == p[j] || p[j] == '.') 时，当前 p[j..j+1] 消去 s[i]bool p2 = (s[i] == p[j] || p[j] == '.') && recursive(s, p, i + 1, j, dp);res = p1 || p2;}}dp[i][j] = res ? 1 : 2;return res;}bool isMatch(string s, string p) {// 记忆化搜索// dp[i][j] == 0，表示没算过// dp[i][j] == 1，表示算过，答案是 true// dp[i][j] == 2，表示算过，答案是 falsevector<vector<int>> dp(s.size() + 1, vector<int>(p.size() + 1, 0));return recursive(s, p, 0, 0, dp);}
};
- 严格位置依赖的动态规划
#include <iostream>
#include <vector>using namespace std;class Solution {
public:// 根据递归改写bool isMatch(string s, string p) {int n = s.length();int m = p.length();vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1));dp[n][m] = true;for (int j = m - 1; j >= 0; j--)dp[n][j] = j + 1 < m && p[j + 1] == '*' && dp[n][j + 2];for (int i = n - 1; i >= 0; i--) {for (int j = m - 1; j >= 0; j--) {if (j + 1 == m || p[j + 1] != '*') {dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i + 1][j + 1];} else {dp[i][j] = dp[i][j + 2] || ((s[i] == p[j] || p[j] == '.') && dp[i + 1][j]);}}}return dp[0][0];}
};
44. 通配符匹配
- 暴力递归
#include <iostream>
#include <vector>using namespace std;// '?' 表示可以变成任意字符，数量 1 个
// '*' 表示可以匹配任何字符串
class Solution {
public:bool recursive(string s, string p, int i, int j) {// 1. s 没后缀if (i == s.length()) {// 同时 p 也没后缀if (j == p.length()) return true;// p 还剩下一些后缀// 如果 p[j] 是 *，那么 p[j]可以消掉，然后看看再剩下的是不是都能消掉return p[j] == '*' && recursive(s, p, i, j + 1);}// 2. s 有后缀，p 没后缀if (j == p.length()) return false;// 3. 都有后缀// 3.1 j 位置不是 *，那么当前的字符必须能匹配if (p[j] != '*') return (s[i] == p[j] || p[j] == '?') && recursive(s, p, i + 1, j + 1);// 3.2 j 位置是 *，可以选择消掉或者不消掉 s[i]return recursive(s, p, i + 1, j) || recursive(s, p, i, j + 1);}bool isMatch(string s, string p) {return recursive(s, p, 0, 0);}
};
- 记忆化搜索
#include <iostream>
#include <vector>using namespace std;// '?' 表示可以变成任意字符，数量 1 个
// '*' 表示可以匹配任何字符串
class Solution {
public:bool recursive(string s, string p, int i, int j, vector<vector<int>> &dp) {if (dp[i][j] != 0) return dp[i][j] == 1;bool res;if (i == s.length()) {if (j == p.length()) {res = true;} else {res = p[j] == '*' && recursive(s, p, i, j + 1, dp);}} else if (j == p.length()) {res = false;} else {if (p[j] != '*') {res = (s[i] == p[j] || p[j] == '?') && recursive(s, p, i + 1, j + 1, dp);} else {res = recursive(s, p, i + 1, j, dp) || recursive(s, p, i, j + 1, dp);}}dp[i][j] = res ? 1 : 2;return res;}bool isMatch(string s, string p) {vector<vector<int>> dp(s.length() + 1, vector<int>(p.length() + 1));return recursive(s, p, 0, 0, dp);}
};
- 严格位置依赖
#include <iostream>
#include <vector>using namespace std;class Solution {
public:bool isMatch(string s, string p) {int n = s.length();int m = p.length();vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));dp[n][m] = true;for (int j = m - 1; j >= 0 && p[j] == '*'; j--)dp[n][j] = true;for (int i = n - 1; i >= 0; i--) {for (int j = m - 1; j >= 0; j--) {if (p[j] != '*') {dp[i][j] = (s[i] == p[j] || p[j] == '?') && dp[i + 1][j + 1];} else {dp[i][j] = dp[i + 1][j] || dp[i][j + 1];}}}return dp[0][0];}
};
P2918 [USACO08NOV] Buying Hay S
#include <iostream>
#include <vector>using namespace std;// 购买足量干草的最小花费
// 有 n 个提供干草的公司，每个公司都有两个信息
// cost[i] 代表购买 1 次产品需要花的钱
// val[i] 代表购买 1 次产品所获得的干草数量
// 每个公司的产品都可以购买任意次
// 你一定要至少购买 h 数量的干草，返回最少要花多少钱
int main() {int n, h;cin >> n >> h;vector<int> cost(n + 1);vector<int> value(n + 1);int _max = 0;for (int i = 1; i <= n; ++i) {cin >> value[i] >> cost[i];_max = max(_max, value[i]);}// 往外扩充int m = h + _max;// dp[i][j] 表示前 i 个公司里挑公司，购买严格 j 磅干草，需要的最少花费vector<vector<int>> dp(n + 1, vector<int>(m + 1));// 首行为最大值表示没有解fill(dp[0].begin() + 1, dp[0].end(), 0x7fffffff);// 除了 dp[0][0] 是 0dp[0][0] = 0;for (int i = 1; i <= n; ++i) {for (int j = 0; j <= m; ++j) {dp[i][j] = dp[i - 1][j];if (j - value[i] >= 0 && dp[i][j - value[i]] != 0x7fffffff)dp[i][j] = min(dp[i][j], dp[i][j - value[i]] + cost[i]);}}int res = 0x7fffffff;// 至少购买 h 数量的干草，返回最少要花多少钱for (int j = h; j <= m; ++j)res = min(res, dp[n][j]);cout << res << endl;
}
- 空间优化
#include <iostream>
#include <vector>using namespace std;int main() {int n, h;cin >> n >> h;vector<int> cost(n + 1);vector<int> value(n + 1);int _max = 0;for (int i = 1; i <= n; ++i) {cin >> value[i] >> cost[i];_max = max(_max, value[i]);}// 往外扩充int m = h + _max;// dp[i][j] 表示前 i 个公司里挑公司，购买严格 j 磅干草，需要的最少花费vector<int> dp(m + 1, 0x7fffffff);// 首行除了 dp[0][0] 是 0，其他都为最大值表示没有解dp[0] = 0;for (int i = 1; i <= n; ++i) {for (int j = value[i]; j <= m; ++j) {if (dp[j - value[i]] != 0x7fffffff)dp[j] = min(dp[j], dp[j - value[i]] + cost[i]);}}int res = 0x7fffffff;// 至少购买 h 数量的干草，返回最少要花多少钱for (int j = h; j <= m; ++j)res = min(res, dp[j]);cout << res << endl;
}
