题意：给出在最底层的木头的个数，问有多少种堆放木头的方式。要求木头必须互相挨着在一起。

解法：f[i]表示最底层i个木头的堆放木头的方式。注意递推的思想！
只需知道上一层堆放0~i-1个（即最底层堆放i个木头）的方式数就可以利用加法原理得到f[i]。

方法一、用前缀和求解。
由于要求木头挨在一起，上层为1个时，相应有i-1个位置可放；2个时，相应为i-2。即：f[i]=f[0]+f[1]*(i-1)+f[2]*(i-2)...+f[i-1]   f[i-1]=f[0]+f[1]*(i-2)+f[2]+(i-3)... +f[i-2] ==》 f[i]=f[i-1]+f[1]+f[2]+...+f[i-1]=f[i-1]+sum[i-1]（sum[i]表示从f[1]到f[i]的和）

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define N 200000 7 #define mod 100000 8 int sum[N],f[N]; 9 10 int main()11 {12     int T,n;13     scanf("%d",&T);14     f[0]=1,sum[0]=0;//sum[i]:f[1~i]15     for (int i=1;i<=N;i++)16     {17       f[i]=(f[i-1]+sum[i-1])%mod;18       sum[i]=(sum[i-1]+f[i])%mod;19     }20     while (T--)21     {22       scanf("%d",&n);23       printf("%d\n",f[n]);24     }25     return 0;26 }

View Code 1

方法二、用斐波拉契数列。
由上面的式子可推出——f[i]=f[i-1]+(f[i-1]-f[i-2])+f[i-1]=3f[i-1]-f[i-2] 这就是斐波拉契数列的奇数项通式，而推导我不知道，但还是能发现i=1~...时，f[]=1,2,5,12,34.. 而斐波拉契数列为1,1,2,3,5,8,13,21,34...奇数项重合的。

【noi 2.6_9277】Logs Stacking堆木头（DP）