1. 整数划分【不可重复，考虑顺序，完全背包】
思路
题意转为完全背包求解。
代码
int n; cin >> n; for (int i = 0; i <= n; i++) f[i][0] = 1; for (int i = 1; i <= n; i++){ for (int j = 1; 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;
- 压缩一维
g[0] = 1; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) g[j] = (g[j] + g[j - i]) % mod; cout << g[n] << endl;
2. 鸣人的影分身【可重复，不考虑顺序，>=0】
1050. 鸣人的影分身
思路
可重复型 & 二维费用完全背包
题意：n 拆成 m 份的方案数，换句话说就是用 m 个数拼成 n的方案数。
每个数可以选多次（≥ 0 \geq 0≥0），就是完全背包问题，受体积和份数限制，即二维费用完全背包。
f [ i ] [ j ]: 表示体积为 i 时，划分 j 份的方案数。
代码
cin >> n >> m; f[0][0] = 1; for (int i = 0; i <= n; i++) for (int j = 1; j <= m; j++) { f[i][j] = f[i][j - 1]; if (i >= j) f[i][j] = (f[i][j - 1] + f[i - j][j]) % mod; } cout << f[n][m] << endl;
3. 数的划分【可重复，不考虑顺序，>=1】
[编程题]数的划分
思路
与上题不同的是，分的每份都不能为空，即 ≥ 1 \geq 1≥1。
f[i][j]: 表示体积为 i 时，划分 j 份的方案数。
代码
int n, m; cin >> n >> m; vector<vector<int>> f(n + 1, vector<int>(m + 1, 0)); f[0][0] = 1; const int mod = 1e9 + 7; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i && j <= m; j++) { f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod; } } cout << f[n][m] << endl;
