这篇文章上次修改于 399 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
ACM程序课算法笔记2——递推求解
基本方法
- 确认：能否容易的得到简单情况的解？
- 假设：规模为N-1的情况已经得到解决。
- 重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。
1、编程中的空间换时间的思想
2、并不一定只是从N-1到N的分析
问题一：HDOJ2050——折线分割平面
问题描述：
平面上有n条折线，问这些折现最多能将平面分割成多少块。
解题思路：
通过画图可得，每次新的折线和旧的折线之间，若交点最多，则新分出的块越多，此时可以根据作画得出第n条折线，最多会产生4(n - 1)个交点，再通过寻找交点和新产生的块的数量有4(n - 1) + 1 ，可得
递推公式：
F(n) = F(n - 1) + 4 (n - 1) + 1
问题二：HDOJ2046——骨牌铺方格
问题描述：
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数。例如n=3时,为2× 3方格，骨牌的铺放方案有三种
解题思路：
我们考虑左往右数的第n个方块，它有两种情况，一种情况是以横着的板子覆盖，一种是被竖着的板子覆盖，以此想法，可得
递推公式：
F(n) = F(n -1) + F(n - 2)
问题三：HDOJ1297——Children’s Queue
问题描述：
输入一个数字N，代表一个儿童队伍的长度，这个队伍有这个要求，女生必须结伴站（相邻）。
问满足条件的队伍有几种？
解题思路：
对此，先考虑简单情况的解
F(1) = 1 | F(2) = 2 | F(3) = 4 | F(4) = 7
现在来考虑递推
对于F(n)的第n个人，可以是男生也可以是女生
当最后一个人是男生，那么对于(n - 1)长度的任意合法队列，都是可行的，情况数量为F(n - 1)
当最后一个人是女生，那么第n-1个人也必定是女生，对于所有(n-2)长度的任意合法队列，都是可行的，情况数量为F(n - 2)
但不仅如此，对于所有(n-2)长度的部分非法队列也是可能的，这种非法队列就是第n-2是女生 第n-3是男生，情况数量为F(n - 4)
可得递推公式：
F(n) = F(n -1) + F(n - 2) + F(n - 4)
问题四：HDOJ 2045 —— LELE的RPG难题
问题描述：
输入N，对于N个格子，有红粉绿三种颜料进行涂色，要求相邻的格子，首尾的格子颜色不一样。
问满足条件的涂法有几种？
解题思路：
对此，先考虑简单情况的解
F(1) = 3 | F(2) = 6 | F(3) = 6(*非常重要)
现在来考虑递推
对于F(n)的第n个格子，对于长度为(n-1)的任意合法序列，因为它首尾不同，故最后一个格子只有一种颜色的涂法，情况数量为F(n - 1)
对于F(n)的第n个格子，对于长度为(n-1)的首尾相同的非法序列，最后一个格子有两种颜色的涂法。长度为(n-1)的首尾相同的非法序列去掉最后一个格子，就是合法序列，故有F(n - 2)，又因为两种颜色的涂法，故有2 * F(n - 2)。
可得递推公式：
F(n) = F(n -1) + 2 * F(n - 2)
问题五：HDOJ1465——不容易系列之一
问题描述：
输入N，有N个信封，每个信封对应一个信箱，现在有以下要求，所有信封和信箱都不对应（都投错了）。
问满足条件的情况有几种？
解题思路：
对此，先考虑简单情况的解
F(1) = 0 | F(2) = 1 | F(3) = 2
现在来考虑递推
对于F(n)的第n封信，对于任意长度为(n-1)的任意合法方案，我新增的一封信可以与之前的任一信封交换来符合条件，情况数量为(n - 1) * F(n - 1)
任意长度为(n-1)的非法方案，只能是只有一个信封信箱对应，其他(n-2)全部装错的情况。然后新增的一封与对的那一封交换，信封信箱对应的那个可以在(n-1)种位置，对于这种非法情况有(n - 1) * F(n - 2)种，然后再乘以1（新增只能和信封信箱对应的进行交换）
可得递推公式：
F(x) = (n - 1) * ( F(n -1) + F(n - 2) )
