整数划分

将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。

Input

输入1个数N(1 <= N <= 50000)。

Output

输出划分的数量Mod 10^9 + 7。

Sample Input

6

Sample Output

4

题意：给出一个数n，求n能被分成几个集合，使每个集合内的数相加的和等于n。

思路：这个题用dp做，dp【i】【j】表示将i分为j个数相加。当 i 等于9，j 等于3时，dp【i-j】【j】即dp【6】【3】等于1，因为6能被分为1，2，3一种，dp【i-j】【j-1】即dp【6】【2】可分为（1，5）和（2，4）两种而dp【9】【3】恰好等于3，所有dp【i】【j】=dp【i-j】【j】+dp【i-j】【j-1】.状态转移方程写出后还要知道数字n最多可分为sart（2*n）位相加。然后for循环逐一加上即可，代码如下：

#include<stdio.h>
#include<math.h>
int a[50010][350];
int main()
{
    int n,i,j,k;
    while(~scanf("%d",&n))
    {
        a[0][0]=1;
        int sum=0;
        k=sqrt(2*n);
        for(i=1;i<=n;i++)
        {
             for(j=1;j<=k;j++)
             {
                if(i>=j)
                a[i][j]=(a[i-j][j]+a[i-j][j-1])%1000000007;
             }
        }
        for(i=1;i<=k;i++)
            sum=(sum+a[n][i])%1000000007;
        printf("%d\n",sum);
    }
    return 0;
}