首页 > 代码库 > 整数划分优化,时间复杂度O(n*sqrt(n))

整数划分优化,时间复杂度O(n*sqrt(n))

基准时间限制:1 秒 空间限制:131072 KB 
将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示例
6
Output示例
4


常见的方法是行不通的,这里dp[i][j]表示的是j个数字和为i的情况
dp[i][j] = dp[i - j][j - 1] + dp[i - j][j]
我的理解是:既然j个数字和为i,那么每个数字减去1,总共减去j即dp[i-j][x],再考虑x的情况,因为因为j个数字中可能出现1也可能不出现1,但是不可能出现多个1,所以x的情况为j-1或者j。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1<<28;
const int maxn=50010;
const int maxm=1e2+10;
const int mod=1e9+7;
int dp[maxn][400];
int maxlen(int x)//最大长度
{
    int ans=sqrt(x*2);
    if(ans*(ans+1)<=2*x)
        return ans;
    else
        return ans-1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n))
    {
        cls(dp,0);
        for(int i=1;i<=n;i++)
            dp[i][1]=1;
        for(int i=2;i<=n;i++)
        {
            int maxj=maxlen(i);
            for(int j=1;j<=maxj;j++)
            {
                dp[i][j]=(dp[i-j][j-1]+dp[i-j][j])%mod;
            }
        }
        int ans=0;
        for(int i=1;i<=maxlen(n);i++)
            ans=(ans+dp[n][i])%mod;
        printf("%d\n",ans);
    }
    return 0;
}

 

整数划分优化,时间复杂度O(n*sqrt(n))