题目链接：https://www.acwing.com/problem/content/description/902/
题目描述
一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。输入描述
共一行，包含一个整数 n。
输出描述
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 109+7 取模。
1≤n≤1000示例
输入
5
输出
7
借鉴完全背包问题求解
切入点
通过分析整数划分这个问题，我们可以发现它与完全背包问题具有一定的相似性。待划分的整数相当于背包的容量，要划分成的数字相当于要装入背包的物品。因此，我们就会想到化用完全背包问题的状态转移方程。
状态表示
f(i,j)表示满足如下条件划分方案的数量：
- 划分成的数字小于等于i
- 划分后的数字的总和等于j
注意于完全背包的不同，此处的f(i,j)表示的是方案数不是最大值。
状态划分与计算
与完全背包相同，对于f(i,j)我们划分如下：
- 用了0个i，方案数即f(i-1,j)
- 用了1个i，方案数即f(i-1,j-i)
- 用了2个i，方案数即f(i-1,j-2*i)
·········
因此，初步的状态转移方程为：
f(i,j)=f(i-1,j)+f(i-1,j-i)+··· （j-k*i>=0）
在完全背包问题中，我们通过等价变形状态转移方程进行了优化，此处我们也进行尝试：
f(i,j)=f(i-1,j)+f(i-1,j-i)+f(i-1,j-2*i)···
f(i,j-i)=f(i-1,j-i)+f(i-1,j-2*i)+···
因此，优化后的状态转移方程为：
f(i,j)=f(i-1,j)+f(i,j-i)
最后，与完全背包一样，可以将f(i,j)降为一维优化，不再赘述，AC代码为一维版本。
初始边界处理
显然：
f(i,0)=0
f(0,i)=0
考虑一下f(0,0)，不划分与之对应，f(0,0)=1，只要从f(i,j)的意义上入手，所有f(i,j)保持一致，应该就能确定正确的初始值。
如果感觉不保险，就用边界值代进去试试，在这里就用f(1,1)，f(1,1)算出来对就行。
另一种思路
状态表示
f(i,j)为满足如下的条件的划分方案数：
记划分一的方案数为x，划分二的方案数为y。
我们将划分一中每个方案的那个1去掉，得到的新方案与原方案数量一致，将新方案集合与f(i-1,j-1)对照。首先，划分一中的方案将变成和为i-1,共j-1项，符合f(i-1,j-1)的状态要求，所以x<=f(i-1,j-1)。再将f(i-1,j-1)所代表的方案均加上一个1，将变成和为i，共j项，符合划分一，即f(i-1,j-1)<=x。所以，x=f(i-1,j-1)。
同理，我们将划分二中每一项减去1，将新方案集合与f(i-j,j)对照。可以得到y=f(i-j,j)，证明方法同上，不再赘述。
综上，状态转移方程为：
f(i,j)=f(i-1,j-1)+f(i-j,j)
另外，这个无法优化成一维，因为得到f(i,j)需要上面几行的数据，必须存储下来以供计算。
完全背包思路的AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1001;
const int mod = 1e9 + 7;
int n;
int f[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;
}非完全背包思路的AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001;
const int mod = 1e9 + 7;
int n;
int f[N][N]; //边界处理 自动初始化为0 没写代码但要知道应该初始化
int main()
{
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;
}
