openOJ 2045 分解数字（DP）

题目链接：http://openoj.awaysoft.com/JudgeOnline/problem.php?id=2045

题意：将n分解成若干个不相同数字之和。有多少种分法？

思路：dp[i][j]表示将i分解成j个数字之和。那么：

（1）j个数字中有1，dp[i][j]=dp[i-(j-1)-1][j-1]，也就是将i-(j-1)-1分成的j-1个数字都加1，并且再增加一个数字1，共j个数字；

（2）j个数字中没有1，dp[i][j]=dp[i-j][j]，也就是将i-j分成的j个数字都加1。

 

int dp[N][320],ans[N];


void init()
{
    int i,j;
    for(i=3;i<=50000;i++)
    {
        dp[i][1]=1;
        dp[i][2]=(i-1)/2;
        ans[i]=dp[i][2];
        for(j=3;j*(j+1)/2<=i;j++)
        {
            dp[i][j]=(dp[i-j][j]+dp[i-j][j-1])%mod;
            ans[i]=(ans[i]+dp[i][j])%mod;
        }
    }
}


int n;


int main()
{
    init();
    rush()
    {
        RD(n); PR(ans[n]);
    }
    return 0;
}