51nod 1201 递推+dp-蒲公英云

51nod 1201 递推+dp

题意：

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

分析：

dp[i][j]表示的是将数字i分成j个不同的数字的划分方法。

这样我们就可以知道，数字n最多的划分数量是1+2+3+……+m <= n ,其中n最大为50000，所以我们可以认为所有的n中最多可以有350个不同的数字组成。

递推公式为：

dp[i][j] = dp[i-j][j] = dp[i-j][j-1] //dp[i-j][j] 表示的是对于数字i-j拆成j个不同数字，那么这j个数字每个数字加上1就得到了i拆成j个不同数字的情况；dp[i-j][j-1]表示的是对于数字i-j拆成j-1个不同数字，那么这j-1个数字每个数字加上1之后在加上数字1就得到了i拆成j个不同数字的情况。

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
#define mod 1000000007
const int maxn = 50005;
int dp[maxn][350];
//dp[i][j]表示的是将i划分成j个不同数字的情况
void cal()
{
    memset(dp,0,sizeof(dp));
    dp[1][1] = 1 ;  //初始化
    for(int i = 2 ; i < maxn ; i++)
    {
        for(int j = 1 ; j < 350 ; j++)
        {
            if(i>j)dp[i][j] = (dp[i-j][j] + dp[i-j][j-1]) % mod ;
        }
    }
}
int main()
{
    cal();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        long long ans = 0 ;
        for(int i = 1 ; i < 350 ; i++)
        {
            ans = (ans + dp[n][i]) % mod ;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}