题目描述(题目难度：简单)
给定一个自然数 N NN，要求把 N NN 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。
注意:
拆分方案不考虑顺序；
至少拆分成 2 个数的和。
求拆分的方案数 m o d modmod 2147483648 的结果。
输入格式
一个自然数 N。
输出格式
输入一个整数，表示结果。
数据范围
1≤N NN≤4000
输入样例：
7
输出样例：
14
来源:acwing
原题传送门
解题报告
题意解读
对于样例中的7。
两个数相加的情况：
1+6
2+5
3+4
这里有3个
三个数相加的情况
1+1+5
1+2+4
1+3+3
2+2+3
这里有4个
四个数相加的情况
1+1+1+4
1+1+2+3
1+2+2+2
这里有3个
五个数相加的情况
1+1+1+1+3
1+1+1+2+2
这里有2个
六个数相加的情况
1+1+1+1+1+2
这里有1个
七个数相加的情况
1+1+1+1+1+1+1
这里有1个
DP分析
这里是的最后状态转移方程的由来是省略了一定步骤的，假如看着有点迷糊的小伙伴可以看看这这篇文章中对完全背包的解读
参考代码
//完全背包求方案数问题 //把1~n-1个数看成n-1种物品。 物品可以无限用，背包容积为n，用f[j]表示和为j的方案数 #include <iostream> #include <algorithm> using namespace std; //int的范围是 -2,147,483,648 到2,147,483,647 typedef long long LL; const int N = 4010; const LL mod = 2147483648; LL f[N];//f[i][j]只从前i个物品中选择，和为j的方案数。 int main() { int n; cin >> n; //初始化处理0这个数的和的方案数是1 f[0] = 1; for(int i = 1;i < n;i++) //为了防止重复计算，要从i开始 for(int j = i;j <= n;j++) f[j] = (f[j] + f[j-i]) % mod;//这里直接优化为一维的形式了，因为这个题中每个数是没有价值的，就忽略价值w[i] cout << f[n] << endl; return 0; }
