递推说白了就是找规律，然后写出他的递推方程，有的还可以写出通项公式，然后准确预测出第n项的值。因为这种规律存在着前因后果的关系，即是说，后一项的结果往往和前一项或前几项有着某种联系。这种联系不仅仅存在于数字之中，世间万物亦是如此。

　　由于，递推是深入理解动态规划的基础，就我目前的水平，看到动态规划就如看到tiger一般，完全不知所以，所以为了找回在动态规划前的自信，我打算在回家之前，找一个递推专题练练手。现记录如下：

　　心得：

　　1. 既然是递推题，那么肯定有递推方程，那么同样有规律可循，既然有规律。所以，若一时做不出来。我们可以用计算机枚举出比较的小的情况，然后找出其中规律。最后AC之。

　　2.有时，当n比较大时，递推起来肯定会耗时，就有可能造成TLE，那么这时不要忘了我们的矩阵君。把数的公式用矩阵表示出来再算，那是大大的方便啊。

　　整个专题地址：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=65818#overview

　　1.　HDU 2041

　　分析：容易知道，可以有两种方式走到第m阶，一是从m-1阶走一步，二是从m-2阶走两步，故F(m)=F(m-1)+F(m-2)。其中边界条件F(1)=0,F(2)=1。这道题用递归做，离线也会超时。

　　2. 　HDU 2042

　　分析：这题直接根据题意列公式即可：3*Pow(2, n)+2-Pow(2, n+1)即是答案。

　　3.     HDU 2044

　　分析：我们用F(n)表示从蜂房1走到蜂房n的路线总数，根据题目条件可得，走到蜂房n只可能经过蜂房n-1和蜂房n-2，故有F(n)=F(n-1)+F(n-2)。题目要求从蜂房a到蜂房b的路线，只需分别把a，b向左移动a-1即可，即F(b-a+1)就是所求。

　　4. 　HDU 2045

　　分析： 共三种颜色，相邻和首尾不能同色。根据题意可作出下图：

红线是非法情况，F(n)表示长为n的方格的总的合法染色数，根据图很容易知道，F(n-1)的每个合法组合分别在F(n)中会产生一个非法组合和一个合法组合，非法组合在F(n)中产生两个合法组合，所以可得公式：F(n)=Pow(2,n-1)-F(n-1)。

　　我们还可以继续分析上图，F(n-1)的合法组合在F(n)中产生F(n-1)个合法组合，而其余的合法组合是F(n-1)的非法组合产生的，共有2*F(n-1)的非法组合，而F(n-1)的非法组合等于F(n-2)。故有：F(n)=F(n-1)+2*F(n-2)。

　　更一般的：假设现有k种颜色，其余条件不变。有公式：F(n)=(k-2)*F(n-1)+(k-1)*F(n-2)，{n>=4}。F(1)=k, F(2)=k*(k-1), F(3)=K*(k-1)*K(k-2)。

　　5. HDU 2018

　　分析：设F(n)表示第n年的牛的总数，显然有关系式：F(n)=F(n-1)+F(n-3)，边界条件为F(1)=1,F(2)=2,F(3)=3。表示今年牛的总数等于去年牛的总数加上今年新生的牛的总数。

递推专题笔记