整数划分

将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("%dn",sum);
}
return 0;
}

最后

以上就是如意凉面为你收集整理的整数划分的全部内容，希望文章能够帮你解决整数划分所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。