讨论 / 讨论f[i]=f[i-1]*2-f[i-m-1]
sanlvlang 2012-09-08 15: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];

有不妥的地方还请大牛指教

#1 zhhyoi@2009-09-20 17:37:00
回复 删除

#2 虺文忠@2009-09-20 19:27:00
回复 删除
你直接记忆化搜吧……

比递推好想得多!

#3 zmh@2010-04-09 11:32:00
回复 删除
f[i]:=f[i-1]*2-f[i-m-1];
#4 a15130609301@2012-09-08 15:10:00
回复 删除
数据用什么啊 int64?
查看更多回复
提交回复