【模板题】计数类DP（整数划分）

【题目描述】
一个正整数 n n n可以表示成若干个正整数之和，形如： n = n 1 + n 2 + … + n k n=n_1+n_2+…+n_k n=n1​+n2​+…+nk​，其中 n 1 ≥ n 2 ≥ … ≥ n k , k ≥ 1 n_1≥n_2≥…≥n_k,k≥1 n1​≥n2​≥…≥nk​,k≥1。
我们将这样的一种表示称为正整数 n n n的一种划分。
现在给定一个正整数 n n n，请你求出 n n n共有多少种不同的划分方法。

【输入格式】
共一行，包含一个整数 n n n。

【输出格式】
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 1 0 9 + 7 10^9+7 109+7取模。

【数据范围】
1 ≤ n ≤ 1000 1≤n≤1000 1≤n≤1000

【输入样例】

5

【输出样例】

7

思路1：f[i][j]表示从1~i中选且总体积恰好为j的方案(完全背包问题)

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + ... + f[i - 1][j - k * i]
f[i][j - i] =           f[i - 1][j - i] + ... + f[i - 1][j - k * i]
因此f[i][j] = f[i - 1][j] + f[i][j - 1]

代码

#include 
#include 
using namespace std;

const int N = 1010, MOD = 1e9 + 7;
int f[N];
int n;

int main()
{
	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;
}

思路2：f[i][j]表示所有总和是i且恰好表示成j个数的和的方案

将状态集合分为最小值是1与最小值大于1两种状态
若最小值是1，则去掉1之后状态为总和是i-1且恰好表示成j-1个数的和，即f[i - 1][j - 1]
若最小值大于1，则将每个数减去1后总和将减去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][n]

代码

#include 
#include 
using namespace std;

const int N = 1010, MOD = 1e9 + 7;
int f[N][N];
int n;

int main()
{
	cin >> n;
	f[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)//总和为i最多用i个数表示
			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;
}