关于递归与递推的那七道题
递归与递推是动态规划最底层的东西，掌握好它对于彻底的理解动规是至关重要的，这次做的题不难，但是它很能锻练人的思维，每一道题都有多种解法。只要静下心来想，一般人都能做出来，而在做题的过程中，你会有很大的收获。
1、一只小蜜蜂...
题目是这样的，有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
对于这种题目，我们首先得找出蜂房之间的关系，如从1只能走到2和3，从2只能走到3和4，从3只能走到4和5??，因此 我们可以得到它们的递推关系： f[a] = f[a+1]+f[a+2]；
下面我们再来找出口，把这个问题化简，即当a与b相邻时(a+1=b 或a+2=b)，f[a] = 1，所以这个问题可以解决了。它就是一个递归，遇到b就结束。为了减少重复访问，我们可以用记忆化搜索来提高效率。
这个题也可以顺着来推，即从a到a有0条路线，从a到a+1有1条路线,从a到a+2有1条路线，而a+3的路线条数来源于a+1 和a+2的路径条数。 f[a] = 0; f[a+1] = 1; f[a+2] = 1;
f[a+3] = f[a+1]+f[a+2]; ??
f[b] = f[b-1]+f[b-2];
由上面的式子就可以看出，它就是一个菲波拉契数列。 2、LELE的RPG难题
题目描述：有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法. 以上就是著名的RPG难题. 解法一：
这个题目经过同学们的讨论，得出了三种解法。我所用的方法还是搜索，我们先不考虑它的限制条件，把第一个格子看成是树的根，那么总共可以建成三棵树，每一棵树的结点都有三个孩子。我们的目标就是要统计这三棵树中分别从根结点走到叶子结点的总的路径条数。然后把限制条件加上，把不符合要求的路径去掉，即可得出最终的结果。具体的做法同样是记忆化搜索. 解法二：递推公式 f[n] = 3 * 2^(n-1) – f[n-1]； 解法三：数学公式 f[n] = (k-1)^n+(k-1)*(-1)^n； 证明略。 3、骨牌铺方格
题目描述：在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 法一：
这道题目，我是用数学方法解的，可以说是枚举。骨牌放入方格中只有两种方式，横放或竖放，设横放的有x张，竖放的有y张。则X+y = n；并且x只能是偶数(要把方格填满，横着放的骨牌只能是成对出现)，而题目给出n最大为50,所x,y完全可以很快的枚举
出来。剩下的工作只需对由x/2，y组成的多重集合进行排列就行了。这个集合中共有两类不同类型的元素，第一类元素的重数k1=x/2， 第二类元素的重数k2=y；故最后的结果为(k1+k2)!/(k1! * k2!)。 法二：
假设f[n]为铺放方案的总数，我们只考虑最后放的那几张骨牌，有两种可能，一种是只放一张，竖着放，此时的方案总数为f[n-1]，还有
一种可能是放两张，横着放，此时的方案总数为f[n-2]。因此我可以得出递推公式 f[n] = f[n-1]+f[n-2]。 法三：
记住这个结论：2*n棋盘用多米诺牌完美覆盖的方法数为一个斐波那契数列，f[0] = f[1] = 1，
f[n] = f[n-1]+f[n-2]。 4、阿牛的EOF牛肉串 题目是这样的：
要构造一个长度为n的只由\三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,但是禁止在串中出现O相邻的情况，问总共有多少种构造方法。
这个题跟第2题一样，用记忆化搜索就可以把它搞定。
有牛人通过猜想，找规律也把它做出来了。可以观察到，当n=1时，有f[n] = 3，当n=2时，有f[n] = 8，当n=3时，我们可以看出
f[n] = 22，由此找出规则f[n] = 2*(f[n-1] + f[n-2])。用这个公式交上去，居然也对了。至于证明嘛，我至今还没有想到。
5、6题都是关于错位排列的题目，求错位排列的个数的公式有很多个： f[n] = n!(1-1/1!+1/2!-1/3!+??+(-1)^n*(1/n!))； f[n] = (n-1)(f[n-1]+f[n-2])； f[n] = n*f[n-1]+(-1)^(n-2)；
f[n]表示错位排列的个数。上面三个公式都可以，就看哪个好用。
第6题稍微有点不同，它是求n 个数中有m个错位的排列的个数。只须从这n 个中选出m个数来对它们错排，其余的数不动就行了。 7、求n条折线能够分割平面的最大数目。
我们知道n条直线能够分割平面的最大数目为n*(n+1)/2；
由这个公式，我们可以推出n条折线能够分割的平面的最大数目为2n*(2n+1)/2 – n = 2*n^2-n+1。
很好的递推题：铺磁砖和走格子
这是Matrix67.com的递推专项训练的题目，感觉很好。
*题一：用1 x 1和2 x 2的磁砖不重叠地铺满N x 3的地板，共有多少种方案？
样例输入：2 样例输出：3
先设一个f[i]表示i*3的地板铺的方法,f[1]=1;f[2]=3;
i*3的地板数是这样得到的：(i-1)*3的地板比i*3的地板少的地方全铺上1*1的瓷砖，这有一种铺法；
或者在(i-2)*3的地板比i*3的地板少的地方铺上2*2的瓷砖和2个1*1的瓷砖，这有两种铺法；
所以得到递推式：f[i]=f[i-1]+2*f[i-2];
*题二：从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？ 样例输入：2 样例输出：7
这个我没想出来，看题解才弄明白。。
先设一个f[i]表示恰好走i步且不经过已走的点 共有的走法。
如果向上走，不会出现经过已走的点；如果向左或右，上一步不能是向右或左。
引用题解上的一句话：/*
这一步的选择数= (3*上一步的所有选择中向上走的选择数) + (2*上一步的所有选择中向左、右走的选择数)。上一步的所有选择中向上走的选择数”实际上就是“上上步的所有选择数”即d[i-2] */引用结束
还有一点，就是“上一步的所有选择中向左、右走的选择数” 等于 “上步所有的选择数(即f[i-1])-上步向上的选择数”
也就等于 “上步所有的选择数(即f[i-1])-上上步所有的选择数(即f[i-2])” 所以得到递推式：f[i] = (3*f[i-2]) + 2*(f[i-1]-f[i-2]);
练习：
1、牛的繁殖问题。有位科学家曾出了这样一道数学题：一头刚出生的小母牛从第四个年头起，每年初要生一头小母牛。按此规律，若无牛死亡，第20年头上共有多少头母牛？ 2、兔子繁殖（递推）
一对小兔子一年后长成大兔子；一对大兔子每半年生一对小兔子。大兔子的繁殖期为4年，兔子的寿命是6年。假定第一年年初投放了一对小兔子，试编程计算，第n年末总共会有多少对兔子。n由键盘输入
这是一道关于递推的程序编程题目，但是找不到从问题的递推思路，知道思路的就写一下你的思路就可以了，不用写代码！！我只要知道一下思路就可以了·····
3、问题描述]
楼梯有n级台阶，上楼可以一步上一个台阶，也可以一步上两个台阶。编写一递推程序，计算有多少种不同的走法？
4、现在有100个数按递推排列，其中第一个数是0，第二个数是2，并且从第二个数起每个数的三倍都等于前后两个数之和。问第100个数被6除所得的余数是多少？