51nod 1201 整数划分

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1201
又是一道不看题解我根本想不到的dp题(；´д｀)ゞ
dp[i][j] $dp\left[i\right]\left[j\right]$表示 i $i$这个数是由 j $j$种不同的数组成的
那么怎么转移喃？
你看：
比如 dp[6][3]={1,2,3} $dp\left[6\right]\left[3\right]=\{1,2,3\}$
如果这 j $j$个数要是都加1，是不是就是转移到 dp[i+j][j] $dp[i+j]\left[j\right]$上了
即： dp[9][3]={2,3,4} $dp\left[9\right]\left[3\right]=\{2,3,4\}$，而这种最小都是 2 $2$，那就还阔以再加个 1 $1$
即： dp[10][4]={1,2,3,4} $dp\left[10\right]\left[4\right]=\{1,2,3,4\}$
所以 dp[i][j] $dp\left[i\right]\left[j\right]$阔以向 dp[i+j][j],dp[i+j+1][j+1] $dp[i+j]\left[j\right],dp[i+j+1][j+1]$两个方向转移

那么倒过来：
dp[i][j] $dp\left[i\right]\left[j\right]$就会有两个方向转移而来，就是：
dp[i][j]=dp[i−j][j]+dp[i−j][j−1] $dp\left[i\right]\left[j\right]=dp[i-j]\left[j\right]+dp[i-j][j-1]$

而 i $i$最多就 =1+2+3+...+j=(1+j)∗j2 $=1+2+3+...+j=\frac{(1+j)\ast j}{2}$
所以 i>=j∗j2 $i>=\frac{j\ast j}{2}$
所以 2i−−√>=j $\sqrt{2i}>=j$

#include"iostream"
#include"math.h"
using namespace std;
const int MOD=1e9+7;
int dp[50005][320];
int main()
{
    for(int i=1;i<=50000;i++)dp[i][1]=1;
    for(int i=2;i<=50000;i++)
    {
        for(int j=1;j<=sqrt(i*2)&&j<i;j++)
        {
            dp[i][j]=(dp[i-j][j]+dp[i-j][j-1])%MOD;
        }
    }
    int N;
    while(cin>>N)
    {
        long long sum=0;
        for(int i=1;i<=sqrt(N*2);i++)
        {
            sum+=dp[N][i];
            sum%=MOD;
        }
        cout<<sum<<"\n";
    }
}