题目内容
一个正整数n可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n，请你求出n共有多少种不同的划分方法。
输入格式
共一行，包含一个整数n。
输出格式
共一行，包含一个整数，表示总划分数量。
数据范围
1≤n≤1000
输入样例
5
输出样例
7
题解
根据题，可以思考为由体积为1到n，n个物品，然后有一个体积为n的背包，求一个恰好装满背包的方案数（每种物品可以用无限次）。
一、状态表示
1、集合 所有从1到i中选，总体积恰好是j的选择方法 2、属性 方案数（数量）
二、状态计算
根据背包问题，根据最后第i个物品选择的数量划分集合。 f[i][j] = f[i-1][j]+f[i][j-i] 若当集合改为：所有总和是i，并且恰好表示成j个数的和的方案时，也能做，这里略过。
代码
#include <iostream> #include <algorithm> using namespace std; const int N = 1010,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; }
