f(n)=2*f(n-1)-f(n-2)+f(n-3)来表示不含‘101’的字符串个数（都是1或0组成的序列）这个式子怎么来的

Question

f(n)=2*f(n-1)-f(n-2)+f(n-3)来表示不含‘101’的字符串个数（都是1或0组成的序列） 这个式子怎么来的

Answer 1

说的不是太清楚 根据公式 脑补了一下 题目应该是
对于长度为n 由01组合而成的任意字符串,求其中不包含101子串的个数
首先最关键的是一个简单的推论,即对于任意长度为n的字符串 如果最后一个字符为0,那么其符合要求的组合个数即长度为n-1时符合要求的字符串个数
因为对于任何不包含101子串的字符串 在其尾部加0 仍不包含101
确定这一点之后就好做了
对于长度为n字符串,如果结尾为0 那么不包含101的有f(n-1)个
如果结尾为1,那么前n-1个中不包含101的同样是f(n-1)个
但是加上1之后有可能组成101的格式 要想组成这样的格式 倒数第二个必然是0 于是我们把所有倒数第二个为0的全都去掉 即f(n-2)
可是这样一定会有误伤 因为把001同样给去掉了 误伤的也就是倒数第三位是0的 再把它加回来 于是加上f(n-3)
最终就是f(n-1) + f(n-1)-f(n-2)+f(n-3)
简化一下就是你那个公式了