内容发布更新时间 : 2024/10/23 6:25:52星期一 下面是文章的全部内容请认真阅读。
关于递归与递推的那七道题
递归与递推是动态规划最底层的东西，掌握好它对于彻底的理解动规是至关重要的，这次做的题不难，但是它很能锻练人的思维，每一道题都有多种解法。只要静下心来想，一般人都能做出来，而在做题的过程中，你会有很大的收获。
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的地板，共有多少种方案？