计数DP
整数划分
一个正整数n可以表示成若干个正整数之和 我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n，请你求出n共有多少种不同的划分方法。
完全背包写法
状态表示
类似完全背包 1 ～ i 分为i 个物品 每个物品的体积为i 并且不限制数量 求总体积为j的方案数
f[i][j]表示从1～i选总体积恰好为j的数量
状态计算
优化成一维
与完全背包类似 从小到大枚举即可
f[j]=f[j]+f[j−i]
const int N = 1010; int f[N]; int main() { int n;cin >> n; f[0] = 1; for (int i = 1;i <= n;++i) { for (int j = i;j <= n;++j) { f[j] = (f[j] + f[j - i]) % mod; } } cout << f[n] << endl; return 0; }
另一种解法
状态表示
所有总和是i 并且恰好表示成j个数的和的方案
状态计算
分成两种情况
const int N = 1010; int f[N][N]; int main() { int n;cin >> n; f[0][0] = 1; for (int i = 1;i <= n;++i) { for (int j = 1;j <= i;++j) { f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod; } } int res = 0; for (int i = 1;i <= n;++i)res = (res + f[n][i]) % mod; cout << res << endl; return 0; }
