题意：将N分为若干个不同整数的和，有多少种不同的划分方式，输出Mod 10^9 + 7的结果即可。 N(1 <= N <= 50000)。
题解：由于N是50000，不能用原来 dp[i][j]代表i中j作为划分的最大的数的方法数 来做，这个做法是O(n^2)的。
那么根据其不同整数的性质，其长度一定为sqrt(2*n)，那么dp[i][j]代表i中划分成j份的方法数。
dp[i][j] = dp[i-j][j] + dp[i-j][j-1]
其中从dp[i-j][j]推过来表示在原来的基础上的所有数都+1；dp[i-j][j-1]推过来表示在原来的基础上的所有数都+1，并且再添了一个1上去。
#include<bits/stdc++.h> using namespace std; typedef long long LL; //#pragma comment(linker, "/STACK:102400000,102400000") const double PI = acos(-1.0); const double eps = 1e-6; const int INF=0x3f3f3f3f; const int mod = 1e9+7; const int N = 50000+10; const int M = 2500000; int dp[N][320]; int main() { int n; scanf("%d",&n); memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i = 1 ; i <= n; i++) { for(int j = 1;j*j <= i*2; j++) dp[i][j] = (dp[i-j][j-1]+dp[i-j][j])%mod; } int sum = 0; for(int j = 1; j*j <= n*2; j++) sum = (sum+dp[n][j])%mod; printf("%d\n",sum); return 0; }
