hdu2569递推式为什么是这样?设当悬崖的长度为n时,到达彼岸的方法有F[n]种.F[1]=3,F[2]=9,F[3]=21分为两种情况：(1)第n-2段与n-1段颜色相同,则第n段可以为三种颜色的任意一种：F[n-2]*3以上我理

Question

hdu2569递推式为什么是这样?
设当悬崖的长度为n时,到达彼岸的方法有F[n]种.
F[1] = 3,F[2] = 9,F[3] = 21
分为两种情况：
(1)第n-2段与n-1段颜色相同,则第n段可以为三种颜色的任意一种：
F[n-2] * 3
以上我理解了,然后看了解题报告后,第二点为什么要减一下?
（2）第n-2段与n-1段颜色不同,第n段只能为其中的两种颜色：
(F[n-1] - F[n-2]) * 2

Answer 1

在F[n-1]中的可行解,有一些是n-1和n-2颜色一样的,假设数目为x
有一些是n-1和n-2颜色不一样的,数目为y （这个是第二点要求的）
则有x+y = F[n-1]
对于n-1和n-2颜色一样的情况,一一对应一种n-2的可行解,所以x = F[n-2]
所以 y = F[n-1] - F[n-2]
------------------
如果换一种思维
假设 a[n]表示n步且最后两步不一样的数目
b[n]表示n步且最后两步一样的数目
则有
b[n] = a[n-1]
a[n] = a[n-1] + b[n-1] * 3
n 从3 开始
a[2] = 6
b[2] = 3
F[n] = a[n] + b[n]