[51nod1201]整数划分

题目链接：

51nod1201

神仙DP

设(f[i][j])表示(i)分成(j)个数的划分数，如何转移？

有转移式：(f[i][j]=f[i-j][j-1]+f[i-j][j])

为什么呢？第一种是先加一个划分出来的数(1)，但是为了和之前的所有数不一样，之前的所有数(+1)。

第二种就是所有数(+1)，没有新划分出来的数。

但是直接转移是会爆空间的，我们知道需要这么多状态吗？

(j)个不同正整数拼成的最小数显然是(sum_{k=1}^j k)

那么就有(frac{j(j+1)}2le i)

那么(j)就是根号级别的。

时间复杂度 (O(nsqrt n))

空间复杂度 (O(nsqrt n))

代码：

#include <cstdio>

int n,f[50005][355],s;
const int p=1000000007;

int main()
{
	scanf("%d",&n),f[0][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;true;++j)
			if(j*(j+1)/2<=i)(f[i][j]=f[i-j][j]+f[i-j][j-1])>=p?f[i][j]-=p:0;
			else break;
	for(int i=1;i*(i+1)/2<=n;++i)(s+=f[n][i])>=p?s-=p:0;
	return printf("%d
",s),0;
}