整数划分

103 阅读 0 评论 68 点赞

我是靠谱客的博主如意凉面，这篇文章主要介绍整数划分，现在分享给大家，希望可以做个参考。

将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

复制代码

1
6

Sample Output

复制代码

1
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循环逐一加上即可，代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}