51nod-1201-数位dp

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1201

1201 整数划分

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

将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。

Input示例

Output示例

4
  f[i][j]表示由j个不同的数字组成的和为i的方案个数，有f[i][j]=f[i-j][j]+f[i-j][j-1];
分别表示所有的数字都加上1来组合成和j-1个数字都加上1再添加一个1，由于最小的数字都变为2了所以不会重复。
j的范围为sqrt(N*2),复杂度N*sqrt(N);因为最长的组合方式就是1+2+3+....+j=i。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 LL mod=1e9+7;
 5 int  f[50005][350];
 6 int main()
 7 {
 8     int N;
 9     cin>>N;
10     f[1][1]=1;
11     for(int i=2;i<=N;++i)
12     {
13         int m=sqrt(i*2);
14         for(int j=1;j<=m;++j)
15         {
16             f[i][j]=(f[i-j][j]+f[i-j][j-1])%mod;
17         }
18     }
19     LL ans=0;
20     for(int i=1;i*(i+1)/2<=N;++i)
21         ans=(ans+f[N][i])%mod;
22     cout<<ans<<endl;
23     return 0;
24 }