AcWing.900.整数划分（计数DP）

一个正整数?n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中?n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数?n 的一种划分。

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

输入格式

共一行，包含一个整数?n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 1e9+7?取模。

数据范围

1≤n≤1000

输入样例:

5

输出样例：

7

可以看作完全背包问题：1,2...代表每个物品体积，n代表背包体积
以 f[i][j] 代表：从1~i中选，且总和恰好为j的数量有多少

则集合可以划分为：选0个第i个物品：f[i - 1][ j ]，选1个第i个物品：f[i - 1][j - i]，选2个第i个物品：f[i - 1][j - 2i]，......，选s个第i个物品：f[i - 1][j - si]

就像在分析完全背包问题时一样，我们可以写出下面的式子（由于此时我们要求的是数量，那么我们就要写成相加的形式）：

f[ i ][ j ] = f[i - 1][ j ] + f[i - 1][j - i] +?f[i - 1][j - 2i] +?f[i - 1][j - 3i] +......+ f[i - 1][j - si]?

f[ i ][j - i] = f[i - 1][j - i] +?f[i - 1][j - 2i] +?f[i - 1][j - 3i] +......+f[i - 1][j - si]?

故可以发现：f[ i ][j - i]和f[ i ][ j ]第二项开始就是相同的，故可以直接把状态转移方程写为：

f[ i ][ j ] = f[i - 1][ j ]? +? f[ i ][ j - i]?

然后我们类比完全背包，又可以得到优化后的一维方程：
????????????????????????????????????????????????????????????????f[ j ] = f[ j ] + f[j - i]?

#include<iostream>
using namespace std;
const int N = 1000 + 10;
const int mod = 1e9 + 7;

int n;
int f[N];

int main() {
	cin >> n;
	f[0] = 1;	//如果选0个数，也就是他自己本身了

	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];
	return 0;
}

?另一种做法：
把f[ i ][ j ]表示：所有的总和是i，且恰好表示成j个数的方案的数量

集合划分为：最小值是1，以及最小值大于1两种

对于最小值是1：我们表示为f[i - 1][j - 1]，对于任何最小值为1的方案，我们减去这个1，那么就能得到f[i -1][j -1]这个方案，然后对于f[i - 1][j - 1]这个方案加上这个1，其对应的方案数仍然是f[i - 1][j -1]，故我们可以直接用f[i - 1][j - 1]来表示这个情况。

对于最小值大于1：我们表示为f[i - j][ j ]，对于这些方案，我们把里面所有的数减去1，那么就能得到f[i - j][ j ]这个方案，然后对于f[i - j][ j ]这个方案加上1，其对应的方案数量仍然和f[i - j][ j ]相等，故直接用f[i - j][ j ]来表示这个情况。

这样我们就得到了：

????????????????????????????????????????????????f[ i ][ j ] = f[i - 1][j - 1] + f[i - j][ j ]

???????????????????????????????????????????ans = f[ n ][ 1 ] + f[ n ][ 2 ] + f[ n ][ 3] +......?

#include<iostream>
using namespace std;
const int N = 1000 + 10;
const int mod = 1e9 + 7;

int n;
int f[N][N];

int main() {
	cin >> n;
	
	//也可以初始化0~n的f[i][0] = 0，但体积为0时，f[i][0]的值始终都是f[i-1][0]，所以我们可以直接初始化f[0][0] = 1
	f[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {	//i顶多就能分成i个1
			f[i][j] = f[i - 1][j - 1] + f[i - j][j];
			f[i][j] %= mod;
		}
	}
	int ans = 0;

	for (int i = 1; i <= n; i++) {	//最后要把所有情况的数量加起来
		ans += f[n][i];
		ans %= mod;
	}
	cout << ans;

	return 0;
}

?