递推
1 基础
推荐一篇论文：
IOI2000国家集训队高寒蕊同学的《递推关系的建立及在信息学竞赛中的应用》
要记住：记录和充分利用有用信息，找数据之间的因果联系。

2 实例 - 递推状态
有一种游戏叫《三五七》，说的是
有三堆火柴，个数分别是3，5，7。
两个玩家依次在某一堆拿火柴，但是必须连续拿，拿完以后剩下的火柴自然就被分成两堆。
例如从7的中间拿掉3跟，可能是：
1 1 1 1 1 1 1 => 1 1 1 1 =>变成了两堆火柴1和3
^ ^ ^
或者
1 1 1 1 1 1 1 => 1 1 1 1 =>变成了两堆火柴2和2
^ ^ ^
但是不能这样拿：
1 1 1 1 1 1 1 => 1 1 1 1 =>变成了两堆火柴2和2
^ ^ ^
因为没有拿连续的。每次可以拿任意多根，只要是同一堆中的。可以一次把一堆拿完，但是不能不拿。
拿到最后一根火柴的玩家胜出。

请编程，尽可能好的玩这个游戏。

我们的算法是基于递推的。
有一些状态是“必输”的。对方面临这些状态，无论怎么拿，我们都可以作出相应的决策，使他面临下一个
“必输”状态或者直接输掉。这里的思想就是递推。例如

1 1 就是一个明显的，也是最简单的必输状态。

那么一步可以拿成1 1的就是胜势（我们不说“必胜”，因为不知道其中奥秘的人拿到它也可能走错而输:) ）
也就是：
1 n (n>1)
1 1 n

显然，一般的，这个简单的必输状态是1 1 .. 1(偶数个1)n n,那么可以推出这些状态是“胜势”：
1 1 1..1 n k (n<>k)
1 1 1..1 n n k

现在我们可以看哪些状态是必输 - 也就是无论怎么拿，剩下的状态是“胜势”。显然有：
1 2 3,可以拿成1 2, 1 3, 2 3, 1 1 3, 1 2 2, 1 1 2, 1 1 1 2,都是胜势。
这样，我们每次扩充胜势和必输状态库，因为3 5 7可以拿成的状态是有限的，所以可以完整的构造一个库。

这个游戏是先拿胜，可以拿成：
3 5 6
2 5 7
一些典型的必输状态是：
1 2 3
1 4 5
2 4 6

3 实例 - 递推数据
在规模化问题中，递推的思想是用得比较多的。就是充分的利用已有的数据。
举一个“在M*N的有障碍物矩阵中找最大的矩形空地”的问题。
例如：
.......M
.M......
....M...
......M.
的最大矩形空地用*标出就是：
..*****M
.M*****.
....M...
......M.
面积是 5*2=10
我们可以先记录每个格子的右或者下最远可以到什么地方而没有障碍。
以记录右边最远位置的方法为例
递推式子是：
if empty[i] then rightmost[i-1]:=rightmost[i]
else rightmost[i-1]:=i-1;

对于每一行，从右往左递推。边界是rightmost[m]直接计算。
记录好了以后就依次扫描每个格子作为左上角，枚举它的高度，利用已经求得的rightmost
不停更新最大值数据。

另一些例子是IOI98《天外来客》和IOI99《隐藏的码字》，IOI99《机场跑道》利用递推，减少了很多记录和枚举。