ZJU/ZOJ 1163 The Staircases 解题报告

题目大意是求将n分成两个以上的不重复数字的分法有多少种。

这是一个经典的搭积木问题的模型，可以看成要用i块积木搭j排，每排的积木数不同。如果把这整个积木转90度则变成了最高的那一排的积木数是j块，于是我们可以得到递推式f[i,j]=f[i-j,j-1]+f[i,j-1](1<=j<=i<=n)，f[i,j]表示i块积木堆成最高一排不超过j块积木的方案数，边界条件是f[0,0]=1。则答案所求很明显是f[n,n]-1。空间复杂度可以利用滚动数组优化到O(n)，因此实际编写时会发现这也是一个背包问题的模型……

3003077 2008-07-24 20:25:41 Accepted 1163 FPC 00:00.00 412K IwfWcf@LZOI