当前位置: 代码迷 >> 综合 >> HDOJ-2047 阿牛的EOF牛肉串(递推)
  详细解决方案

HDOJ-2047 阿牛的EOF牛肉串(递推)

热度:96   发布时间:2023-12-09 20:51:19.0

题目: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