![在这里插入图片描述](https://img-blog.csdnimg.cn/20190920152209480.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1llbktvYw==,size_16,color_FFFFFF,t_70)
不多bb,直接开冲,
1.首先从n个开始分析
有两种情况:
第一种情况(非o的):那么n最后可以填e或者f,那么2f(n-1)
第二种情况 (o的):那么n-1只能填e或f了,那么2f(n-2);
得出我们的递归公式
f(n)=2f(n-2)+2f(n-1);
贴上ac的代码: