计数DP

整数划分

一个正整数$n$可以表示成若干个正整数之和 我们将这样的一种表示称为正整数n的一种划分。

现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

完全背包写法

状态表示

类似完全背包 $1～i$分为$i$个物品 每个物品的体积为$i$ 并且不限制数量 求总体积为$j$的方案数

$f[i][j]$表示从$1～i$选总体积恰好为$j$的数量

状态计算

$f[i][j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-i\ast 2]+\cdots +f[i-1][j-s\ast i]$

$f[i][j-i]=f[i-1][j-i]+f[i-1][j-i\ast 2]+\cdots +f[i-1][j-s\ast i]$

$\therefore$$f[i][j]=f[i-1][j]+f[i][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$并且恰好表示成$j$个数的和的方案

状态计算

分成两种情况

①最小值为1 去掉一个1 得$f[i-1][j-1]$表示$j-1$个数的和为$i-1$

②最小值大于1 每个数都减去1 得$f[i-j][j]$ 表示$j$个数的和为$i-j$

$\therefore$$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;
}