DP求方案数类题目汇总
P1164 小A点菜方格取数矩阵整数划分鸣人的影分身糖果波动数列砝码称重地宝取宫
DP求方案数类题目汇总 P1164 小A点菜
【题目链接】P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路：经典01背包求方案数问题（恰好）
f[i][j]：从前i个物品中选，总和恰好为j的所有方案的集合。
属性：count
f[i][j] = f[i - 1][j] + f[i - 1][j - w]
初始化：
f[0][0] = 1;
【代码实现】
二维：
#include#include #include using namespace std; const int N = 1010; int f[N][N];// 从前i个物品中选，总和恰好为j的所有方案的集合 int n, m; int main() { cin >> n >> m; f[0][0] = 1;// 一个都不选 for (int i = 1; i <= n; i ++ ) { int w; cin >> w; for(int j = 0; j <= m; j ++) { f[i][j] = f[i - 1][j]; if(j - w >= 0) f[i][j] += f[i - 1][j - w]; } } cout << f[n][m]; return 0; }
一维：
#include方格取数#include #include using namespace std; const int N = 1010; int f[N];// 从前i个物品中选，总和恰好为j的所有方案的集合 int n, m; int main() { cin >> n >> m; f[0] = 1;// 一个都不选 for (int i = 1; i <= n; i ++ ) { int w; cin >> w; for(int j = m ; j >= w; j --) { if(j - w >= 0) f[j] += f[j - w]; } } cout << f[m]; return 0; }
【题目链接】2067. 走方格 - AcWing题库
思路：数字三角形模型的计数问题
f[i][j]：从（1，1）走到（n，m）的所有可行方案的集合
属性：count
初始化：
f[1][1] = 1;
【代码实现】
#include#include #include using namespace std; const int N = 40; int f[N][N]; int n, m; int main() { cin >> n >> m; f[1][1] = 1;// 初始化 for (int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++) { if(i == 1 && j == 1) continue;// 不能少！！！ if(i % 2 ==0 && j % 2 == 0) continue; f[i][j] = f[i - 1][j] + f[i][j - 1]; } cout << f[n][m]; return 0; }
思路二：dfs（数据量小嘛）—— 部分分数
#include#include #include using namespace std; const int N = 40; int n, m; int ans; void dfs(int x, int y) { if(x % 2 == 1 || y % 2 == 1)// 至少有一项为奇数，说明可以走该点 { if(x == n && y == m)// 走到终点 { ans ++; return ; } if(x < n) dfs(x + 1, y);// x未到n if(y < m) dfs(x, y + 1);// y未到m } } int main() { cin >> n >> m; dfs(1, 1); cout << ans; return 0; }
偏移方向：
#include矩阵#include #include using namespace std; const int N = 40; int n, m; int ans; bool st[N][N]; int dx[2]={0, 1},dy[2]={1, 0}; void dfs(int x, int y) { if(x == n && y == m) ans ++; for(int i = 0; i < 2; i ++) { int a = x + dx[i], b = y + dy[i]; if(a < 1 || a > n || b < 1 || b > m) continue; if(st[a][b]) continue; if(a % 2 == 0 && b % 2 == 0) continue; st[a][b] = true; dfs(a, b); st[a][b] = false;// 恢复现场 } } int main() { cin >> n >> m; dfs(1, 1); cout << ans; return 0; }
【问题描述】
把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的比左边大，列中下边的比上边的大。一共有多少种方案？
答案很大，你只需要给出方案数除以 2020 的余数即可。
思路：动态规划——数字三角形模型的计数问题
f[i][j]：第一行的数的个数为i，第二行的数的个数为j的所有方案的集合
属性：count
初始化：
f[0][0] = 1;// 一个都不放
注：要求同一行中右边的比左边大，列中下边的比上边的大
【代码实现】
答案：1340
#include整数划分#include #include using namespace std; const int N = 2500, mod = 2020; int f[N][N]; int main() { int n = 1010; f[0][0] = 1;// 一个都不放 for(int i = 1; i <= n; i ++) for (int j = 0; j <= i; j ++ )// 第一行数字的数目必须比第二行大（下方比上方大） { f[i][j] = f[i - 1][j] % mod; if(j - 1 >= 0) f[i][j] = (f[i][j] + f[i][j - 1]) % mod; } cout << f[n][n]; return 0; }
【题目链接】900. 整数划分 - AcWing题库
样例剖析：
5的7种划分如下：
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
思路：
注：未限制选取的个数，可以选择无限次！！！！
把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）
f[i][j]表示前i个整数（1,2…,i）恰好拼成j的方案数
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2*i] + f[i - 1][j - 3*i].....
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2*i] + f[i - 1][j - 3*i] .....
因此：f[i][j] = f[i - 1][j] + f[i][j - i]（类似完全背包的推导！）
即一维：f[j] = f[j] + f[j - i]
初始化：当一个数都不选的时候，只有一种方案
即：for (int i = 0; i <= n; i ++)f[i][0]= 1;
等价变形后： f[0] = 1
【代码实现】
二维：
#includeusing namespace std; const int N = 1e3 + 7, mod = 1e9 + 7; int f[N][N]; int main() { int n; cin >> n; for (int i = 0; i <= n; i ++) { f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案 } for (int i = 1; i <= n; i ++) { for (int j = 0; j <= n; j ++) { f[i][j] = f[i - 1][j] % mod; if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod; } } cout << f[n][n] << endl; }
一维：
#include鸣人的影分身#include #include using namespace std; const int N = 1010, mod = 1e9 + 7; int dp[N]; int main() { int n; cin >> n; dp[0] = 1;// 容量为0时，前 i 个物品全不选也是一种方案 for(int i = 1; i <= n; i ++) for(int j = i; j <= n; j ++) dp[j] = (dp[j] + dp[j - i]) % mod; cout << dp[n]; return 0; }
【题目链接】1050. 鸣人的影分身 - AcWing题库
注：限制选取的个数，不再是完全背包的模型！！！！—— 与整数划分的区别所在（且状态表示也不是前i个数，而是分为了j个数）！！！
思路：
初始化：
f[0][0] = 1;// 一个都不选,其它状态都是不合法的
【代码实现】
#include#include #include using namespace std; const int N = 30; int f[N][N];// f[i][j]：总和为i，且分成j个数的集合 int m, n; int main() { int T; cin >> T; while(T --) { cin >> m >> n; memset(f, 0, sizeof f); f[0][0] = 1;// 一个都不选 for(int i = 0; i <= m; i ++)// 鸣人的查克拉可以为0 for(int j = 1; j <= n; j ++) { f[i][j] = f[i][j - 1]; if(i - j >= 0) f[i][j] += f[i - j][j]; } cout << f[m][n] << endl; } return 0; }
DFS组合类型深搜：
【代码实现】
#include糖果#include #include using namespace std; int m, n; int ans; void dfs(int u, int power, int start)// u为第几个盘子，power为当前能量，选的这个数为start（保证升序选择几个苹果） { if(u == n + 1) { if(power == 0) { ans ++; } return ; } if(start > power) return ;// 可行性剪枝 for(int i = start; i <= m; i ++) { dfs(u + 1, power - i, i); } } int main() { int T; cin >> T; while(T --) { cin >> m >> n; ans = 0;// 多组数据 dfs(1, m, 0); cout << ans << endl; } return 0; }
【题目链接】1047. 糖果 - AcWing题库
思路：01背包的扩展
初始化：求最值（大）问题，无效方案要初始化为负无穷！！！
memset(f, -0x3f, sizeof f);// f[i][0], f[0][i]这些都不合法
f[0][0] = 0;// 注：本题求的是价值而不是方案，所以初始化为0而不是1！！！
【代码实现】
#include波动数列#include #include using namespace std; const int N = 110; int f[N][N]; // f[i][j]：前i个物品中选，且 糖果总数 % k(余数) 为 j 的所有方案的集合 // 属性 max // 不选第i个物品：f[i, j] = f[i - 1, j] // 选！：f[i][j] = f[[i - 1][j - w % k] + ---- 为了防止负数 [j - w % k] ---> [(j - w % k + k) % k] int get_mod(int a, int b)// a % b的正余数结果 { return (a % b + b) % b; } int main() { int n, k; cin >> n >> k; // 求的最大值 memset(f, -0x3f, sizeof f);// f[i][0], f[0][i]这些都不合法 f[0][0] = 0;// 注：本题求的是价值而不是方案，所以初始化为0而不是1！！！ for (int i = 1; i <= n; i ++ ) { int w; cin >> w; for (int j = 0; j < k; j ++ )// 余数：0~k - 1 f[i][j] = max(f[i - 1][j], f[i - 1][get_mod(j - w, k)] + w); } cout << f[n][0]; return 0; }
【题目链接】1214. 波动数列 - AcWing题库
tips：此题也请与第3题——糖果对比
思路：
S
−
(
n
−
1
)
d
1
+
(
n
−
2
)
d
2
+
…
+
d
n
−
1
n
=
x
frac {S−(n−1)d1+(n−2)d2+…+dn−1}{n}=x
nS−(n−1)d1+(n−2)d2+…+dn−1=x
x为正整数，则说明分子一定是n 的倍数，简单可证 S%n 与 ((n−1)d1+(n−2)d2+…+dn−1)%n余数相同时，分子为n的倍数。则最终f[n−1][s%n]的方案数，就是 (n−1)d1+(n−2)d2+…+dn−1这 n−1个 d的合法方案数，两者是等价的。
初始化：求方案数
f[0][0] = 1;// f[i][0], f[0][i]都是不合法的
【代码实现】
#include砝码称重#include #include using namespace std; const int N = 1010, mod = 100000007; int f[N][N]; int get_mod(int a, int b)// 正数mod { return (a % b + b) % b; } int main() { int n, s, a, b; cin >> n >> s >> a >> b; f[0][0] = 1; // 一个都不选的方案为1，其它都为不合法方案 for (int i = 1; i < n; i ++ )// n - 1个物品 for(int j = 0; j < n; j ++)// 枚举余数：0 ~ n - 1 { f[i][j] = (f[i - 1][get_mod(j - a * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)]) % mod; } cout << f[n - 1][get_mod(s, n)]; return 0; }
【题目链接】3417. 砝码称重 - AcWing题库
【题目链接】
三种选择方式：
1.不选第i个物品
2.第i个物品放左边（负）
3.第i个物品放右边（正）
状态表示：f[i][j]：从前i个物品中选，且重量为j的所有方案的集合
属性：bool：是否非空
初始化：f[0][0] = true
【代码实现】
#include地宝取宫#include #include using namespace std; const int N = 110, M = 2e5 + 10, B = M / 2;// 偏移量 int n, m; int w[N]; bool f[N][M]; int main() { cin >> n; for (int i = 1; i <= n; i ++ ) { cin >> w[i]; m += w[i]; // 总重量 } f[0][0 + B] = true;// 初始化 for (int i = 1; i <= n; i ++ ) for(int j = -m; j <= m; j ++)// 枚举重量：范围-m ~ m（-m可能很小，为保证下标不为负数 要加偏移量） { f[i][j + B] = f[i - 1][j + B]; if(j + w[i] <= m) f[i][j + B] |= f[i - 1][j + w[i] + B]; if(j - w[i] >= -m) f[i][j + B] |= f[i - 1][j - w[i] + B]; } int ans = 0; for (int j = 1; j <= m; j ++ ) if(f[n][j + B]) ans ++; cout << ans; return 0; }
遇到就会汇总进来~
状态的含义、表示初始化枚举顺序等缺一不可！
参考文献：
acwing蓝桥杯辅导课
洛谷题库
