计数dp原理
计数DP
整数划分
一个正整数 n n n可以表示成若干个正整数之和 我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n,请你求出n共有多少种不同的划分方法。
完全背包写法
状态表示
类似完全背包 1 ~ i 1~i 1~i分为 i i i个物品 每个物品的体积为 i i i 并且不限制数量 求总体积为 j j j的方案数
f [ i ] [ j ] f[i][j] f[i][j]表示从 1 ~ i 1~i 1~i选总体积恰好为 j j j的数量
状态计算
f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − i ] + f [ i − 1 ] [ j − i ∗ 2 ] + ⋯ + f [ i − 1 ] [ j − s ∗ i ] f[i][j] \qquad = f[i-1][j] + f[i - 1][j - i] + f[i-1][j - i * 2]+\cdots + f[i-1][j - s * i] f[i][j]=f[i−1][j]+f[i−1][j−i]+f[i−1][j−i∗2]+⋯+f[i−1][j−s∗i]
f [ i ] [ j − i ] = f [ i − 1 ] [ j − i ] + f [ i − 1 ] [ j − i ∗ 2 ] + ⋯ + f [ i − 1 ] [ j − s ∗ i ] f[i][j - i] \ \,= \qquad \qquad \quad f[i - 1][j - i] + f[i - 1][j - i * 2] + \cdots + f[i -1 ][j - s*i] f[i][j−i] =f[i−1][j−i]+f[i−1][j−i∗2]+⋯+f[i−1][j−s∗i]
∴ \therefore ∴ f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − i ] f[i][j] = f[i - 1][j] + f[i][j - i] f[i][j]=f[i−1][j]+f[i][j−i]
优化成一维
与完全背包类似 从小到大枚举即可
f [ j ] = f [ j ] + f [ j − i ] f[j] = f[j] + f[j - i] 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 i i并且恰好表示成 j j j个数的和的方案
状态计算
分成两种情况
①最小值为1 去掉一个1 得 f [ i − 1 ] [ j − 1 ] f[i - 1][j - 1] f[i−1][j−1]表示 j − 1 j-1 j−1个数的和为 i − 1 i-1 i−1
②最小值大于1 每个数都减去1 得 f [ i − j ] [ j ] f[i - j][j] f[i−j][j] 表示 j j j个数的和为 i − j i-j i−j
∴ \therefore ∴ f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − j ] [ j ] f[i][j] = f[i - 1][j - 1] + f[i - j][j] f[i][j]=f[i−1][j−1]+f[i−j][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;
}