51nod 1201 整数划分

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

DP转移方程：dp[i][j] = dp[i-j][j]+dp[i-j][j-1];

dp[i][j] 表示将i分成j个不相等的数的个数。

dp[i-j][j]-->dp[i][j]表示给原先的j个数各加一；

dp[i-j][j-1]-->dp[i][j]表示给原先的j-1的数加1，再附带个1.

因为不相等的数，所以n(n+1)/2<=5e4+5,n = 400左右就行。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 5e4+5;
const int mod = 1e9+7;
int dp[maxn][400];
int main()
{
    int n;
    cin>>n;
    dp[0][0] = 1;
    for(int j=1;j<400;j++)
    {
        for(int i=j;i<=n;i++)
        {
            dp[i][j] = (dp[i-j][j]+dp[i-j][j-1])%mod;
        }
    }
    long long ans = 0;
    for(int i=1;i<400;i++)
    {
        ans = (ans+dp[n][i])%mod;
    }
    cout<<ans<<endl;
    return 0;
}