算法学习笔记之递推求解
重点学习：如何把一个大问题分解为几个小问题
导引
我们可以写出上面和下面的公式
例1
n=1 f(n) = 2
n=2 f(n) = 4
n=3 f(n) = 7
......
假设平面上已经有n-1条直线，则第n条直线会与剩下的n-1条之间有n-1个交点，这n-1个焦点将第n条直线划分为了n段，每一段会将一个区域分成两块，于是我们可以写出状态转移方程：f(n) = f(n-1) + n
化简后变成f(n) = n(n+1)/2 + 1
例2
f(1) = 2
f(2) = 7
......
假设平面上已经有n-1条折线，则第n条折线会与剩下的n-1条之间有4(n-1)个交点，这n-1个焦点将第n条折线划分为了4(n-1)+1段，每一段会将一个区域分成两块，于是我们可以写出状态转移方程：f(n) = f(n-1) + 4(n-1) + 1
例3
f(1) = 1
f(2) = 2
f(3) = 3
......
在2xn的长方形方格中，若第一行的最后一个方格(1,n)是竖着铺，则前面的2x(n-1)的长方形方格有f(n-1)种铺设方式；若第一行的最后一个方格(1,n)是横着铺，则前面的2x(n-2)的长方形方格有f(n-2)种铺设方式。故2xn的长方形方格共有f(n-1)+f(n-2)种铺放方式。
可以写出状态转移方程f(n) = f(n-1) + f(n-2)
例4
类比上一例，
若最后一个方格铺1x1，则前面n-1个方格有f(n-1)种铺法；
若最后一个方格铺1x2，则前面n-2个方格有f(n-2)种铺法；
若最后一个方格铺1x3，则前面n-3个方格有f(n-3)种铺法；
我们可以写出状态转移方程：f(n) = f(n-1) + f(n-2) + f(n-3)
总结：递推求解的基本方法
1.确认：能否容易的得到初始状态的解
2.假设：规模不大于N-1的状态已经得到解决
3.重点分析：当规模扩大到N时，如何枚举出所有的情况，然后用子问题的状态表示出最后的状态F(N)
例5
一个学校的校长想要让学生排成一列，但是他又不想女生单独站队，请给出n个学生可能的站队数量
分析1：
若最后一位同学是男生，前面n-1位同学任意站队，若前面n-1位同学站队合法，则有f(n-1)种可能，若不合法，则有0种可能
若最后一位同学是女生，则她前面一个同学一定是女生，前面n-2位同学任意站队，若前面n-2位同学站队合法，则有f(n-2)种可能，若不合法，当其最后一名同学是女生且其前一名同学是男生时，依旧可以合法，此时有f(n-4)种可能。
分析2：
采用二维数组保存站队，0表示最后一名同学是女生，1表示最后一名同学是男生，f(n)表示合法的全部数量，f(n, 1)表示合法的最后一个是男生的数量，f(n, 0) 表示合法的最后一个是女生的数量，则有f(n)=f(n, 0) + f(n, 1)
f(n, 0) = f(n-1, 0) + f(n-2, 1)
f(n, 1) = f(n-1, 1) + f(n-1, 0)
延申：有一个由a,b,c组成的字符串，a不能在b后面，b不能在c后面，计算能组成多少个字符串
分析：采用二维数组保存以字符x结尾的字符串，1表示a，2表示b，3表示c，则能组成f(n)=f(n, 1) + f(n, 2) + f(n, 3)个字符串
f(n, 1) = f(n-1, 1) + f(n-1, 3)
f(n, 2) = f(n-1, 2) + f(n-1, 1)
f(n, 3) = f(n-1)
例6
若第n-1个元素和第一个元素同色，则第n-2个元素和第一个元素肯定不同色（因为之前的序列都是合法的），那么最后一个元素有两种选法，则这种情况的数量为2*f(n-2)
若第n-1个元素和第一个元素不同色，则最后一个格子只有一种选法，故这种情况数量为f(n-1)
例7(卡特兰数)
假设在地上按照顺时针方向依次写下2n个数字1,2,3,4…2n围成一个圆，然后用n条直线连接这2n个数字，每个数字都和一个数字相连，并且仅仅和一个数字相连。要求所有的连线都不能有交点。
请计算一共有多少种不同的连线方式。
思路：
对于数字1，当其与其他2n-1个数连接时，若与奇数连接时，可以发现一定会出现交点。也就是数字1只能与偶数连接。当连接2时，显然有f(n-1)种方法，当连接4时，将2n个数分成了两半，其中一半为f(1)，另一半为f(n-2)，同理，我们可以写出该公式：f(n) = f(n-1) + f(1) * f(n-2)+ ...... + f(n-2)*f(1) + f(n-1)。
显然这是一个卡特兰数
卡特兰数前面若干项分别为：1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786....
公式为：