题目：HDOJ-2047
题目描述：长度为n的字符串，包含’E’ ‘O’ ‘F’三个字符（可以只有其中一种或两种字符），而且不能两个’ O’ 相邻，求长度为n时可能的组合数。（0<n<40）
思路：
重点是逆向推导，利用已求到的f(n-1)、f(n-2)…得到f(n)。
一开始想的太复杂了,一直分析到了n+3，如下：
①f(n-2) n-1 : E/F n : E/F/O 得到 f(n-2) * 2 *3
②f(n-3) n-2 : E/F n-1 : 0 n : E/F 得到f(n-3) * 2 * 2
最终得到f(n)=f(n-2)*6+f(n-3)*4，实际上我这是对n-1位置上的两种情况进行讨论了，其实完全没必要这么麻烦。
递推很重要的一点是已求到的f(m) (m<n) 是一定合法的。
①f(n-1) n : E/F 得到f(n-1) * 2
当n位置上是E/F，前n-1个位置只要合法即可，n位置对前n-1个位置不造成任何影响，所以可以直接套用f(n-1)。
②f(n-2) n-1 : E/F n : O 得到f(n-2) * 2 * 1
当n位置上是O，n-1位置只能为E/F，同理前n-2位置直接套用f(n-2)。
最终得到f(n)=f(n-1)*2+f(n-2)*2
其实一道题的递推公式不止一种形式，不过结果都是一样的，只是分析过程不同。
逆推通常的思路：对n情况进行讨论，对前n-1