sanlvlang 2012-09-08 00:10:00
点我顶贴
收藏
删除
以n=4， m=3 为例:
当 i=3是 f[3]的放法为f[2]*2-1 即减去 1,2,3 都放的情况， 同样的，当i=4 时，由于1，2，3 都放的情况已被我们在处理f[i-1](即f[3]) 时排除（有点Dp的想法）所以f[4]:=f[3]*2减去2，3，4都放的情况，而2，3，4都放的情况是什么？即2，3处都放，也即1处不放（只有1处不放，2，3处才能都放）；然而，我们知道，每个点都有两种方法，放或不放；所以在i<m时有f[i]:=f[i-1]*2 因此：1处不放情况也即 0（1-1：1的前一个)处的所有方法故f[4]:=f[3]*3-f[0] 推广后便是：当i>m时
f[i]:=f[i-1]*2-f[i-m-1]；
有不妥的地方还请大牛指教