目录
- 1、定义及基本思想
- 2、增量法
- 1.兔子产子
- 2.直线分区域
- 3.折线分区域
- 3、分类法
- 1.铺放骨牌（2Xn）
- 2.骨牌铺放（1Xn）
- 3.排队
- 4.涂色
- 4、总结：基本方法
1、定义及基本思想
递推算法是一种通过已知条件逐步推导出结果的算法。它利用一定的递推关系，从初始条件开始，一步步推出后续的结果，直到得到最终答案。其基本思想是通过已知条件和递推关系式，逐步推导出所求问题的解。
当我们求解问题规模为n的问题时，不能只局限于从前几项的数据当中寻找规律，当题目的递归深度稍微深一些时，这种方法很可能就无法奏效了，因此我们需要学习递推求解的思想，掌握其基本思想和步骤，往往很多问题就能迎刃而解。
2、增量法
1.兔子产子
设一对大兔子每月生一对小兔子，每对新生兔在出生一个月后成长为大兔子，假若兔子都不死亡。问：某个繁殖场内有一对小兔子，第n个月繁殖场内有多少对兔子。
我们先想想第五个月有多少对兔子
f(1) = 1,f(2) = 1,f(3) = 2,f(4) = 3,f(5) = 5
现在我们回顾得到答案的过程无非是：
f(5) = f(4) + 新生小兔数量
新生小兔数量则取决于f(4)中大兔的数量，而f(4)大兔的数量为f(3),因为f(3)中无论大兔或者小兔在一个月之后都会成为大兔。
现在我们可以推广
f(n) = f(n-1) + f(n-2)（n>2）
该式子即为递推公式，也即动态规划中的状态转移方程：
假设f（n）为问题规模为n时的状态，则它可以由问题规模更小时的状态f（n-1）等（或常数）表示出来，即由问题规模为（n-1）时的状态转移到了问题规模为n时的状态
2.直线分区域
在一个平面上有一个圆和n条直线，这些直线中每一条在圆内都同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。
与上题相同，我们先想想简单情况
f（1）=2，f（2）=4，f（3）=7
核心问题还是求每增加一条直线时的增量
现在我们画一个圆在纸上，假设圆内已经存在相交的n-1条直线，第n条与所有直线都相交的线上会有n-1个相交点将第n条直线分为n条线段。每条线段的作用为：将线段所在区域一分为二。
由此可以得到状态转移方程：
f（n） = f（n - 1）+ n（n>1）
3.折线分区域
平面上有n条折线（具有一个共同端点的两条射线），这些折线最多能将平面分割成多少块？
与上题类似，不难发现第n条折现与前n-1条折线有4（n-1）个交点，将第n条折线分为4（n-1）+1条线段，则有状态转移方程：f（n）= f（n-1）+4（n-1）+1（n>1）
3、分类法
主要难点为分类，要分出正确的类别，且不同类别之间不会有重复、遗漏
1.铺放骨牌（2Xn）
在2Xn的长方形方格中，用n个1X2的骨牌铺满方格，例如n=3时，为2X3方格。骨牌的铺放方案有三种（如图），输入n，输出铺放方案的总数
第n列的上面那个方格有两种骨牌铺放的可能：竖着放、横着放
不难发现当骨牌竖着放时，则方案总数与f（n-1）相同，当骨牌横着放时，第n-1列和第n列下面的两个放个也只能横着放一个骨牌，此时方案总数为f（n-2），则
竖着放时方案总数：f（n-1）
横着放时方案总数：f（n-2）
状态转移方程：f（n）=f（n-1）+f（n-2）（n>2）
2.骨牌铺放（1Xn）
有个1Xn的长方形，用1X1、1X2、1X3的骨牌铺满方格。例如：当n=3时为1X3的方格（如图），此时共有四种铺法。
与上题类似，本题可分为
当最后一格铺1X1的骨牌时：f（n-1）
当最后一格铺1X2的骨牌时：f（n-2）
当最后一格铺1X3的骨牌时：f（n-3）
所以状态转移方程为：
f（n）=f（n-1）+f（n-2）+f（n-3）（n>3）
3.排队
PHT学校有很多学生。
有一天？校长希望所有学生站成一排，并且规定女孩不能单独站。换句话说，要么队列中没有女孩，要么不止一个女孩站在一起。比如，n=4时候，有以下7种
可能的合法队列（F女生，M男）：
FFPF、FFFM、MFFF、FFMM、MFFM、MMFFS
MMMM
给定人数n，求所有可能的n个人的合法队列数。
由分类法，我们很自然地可以将该队列分为两类：
1.最后一个人为男生
2.最后一个人为女生时，最后第二个人也必须是女生
这一题地难点就在接下来地步骤，如果我们地分类深度到此为止了，那么可能就无法做出这道题
根据题意，该队列还有合法与非法之分，所以我们还要将第1类队列和第2类队列分别再分成前（n-1）个人所组成的队列为合法的队列与非法的队列
当最后一个人为男生且前n-1个人所组成的队列合法时，合法队列数为f（n-1）
当最后一个人为男生且前n-1个人所组成的队列非法时，我们需要思考非法的定义：女生单独站。则此时加上一个男生也无法使队列合法，即合法队列数为0
当最后两个人为女生且前n-2个人所组成的队列合法时，合法队列数为f（n-2）
当最后两个人为女生且前n-2个人所组成的队列非法时，根据上面的思考，我们又可以将队列非法的位置分为两类：如果队列在队尾非法，即倒数第三个人为女生，倒数第四个人为男生，此时加上两个女生可以使队列合法，即合法队列数为f（n-4）；如果队列在队中非法，在队尾加入两个女生无法使队列合法，，即合法队列数为0。则此种情况下合法队列数的总和为f（n-4）
则状态转移方程为：
f（n）=f（n-1）+f（n-2）+f（n-4）（n>4）
4.涂色
有排成一行的n个方格，用红（Red）、粉（Pink）、绿（Green） 三色涂每个格子。每格涂一色，要求任何相邻的方格不能同色，且首尾两格不能同色，求全部的满足要求的涂法。
本题也涉及合法与非法，则可以分类为
前n-1个方格涂色合法，涂法共f（n-1），
前n-1个方格涂色非法，当存在相邻方格共色的情况时，合法的涂法为0；
当前n-1个方格因首尾同色而非法时，可以通过在最后一个方格涂上不同颜色使涂色合法，此时前n-2个方格涂色合法，只需将第n-1个方格涂成第一个方格的颜色，然后最后一个方格在剩下两种颜色中选一种即可，则合法的涂法共2*f（n-2）
则状态转移方程为：
f（n）=f（n-1）+f（n-2）*2
4、总结：基本方法
首先，确认：能否轻易地得到初始状态的解？
然后，假设：规模不大于N-1的状态已经得到解决
最后，分析：当问题规模扩大到N时，如何枚举出所有的情况，然后用子问题的状态（F(1)、F(2)、…F（N-1））表示出最终的状态F（N）（即状态转移）。
