前言\COLOR{WHITE}{前言}前言
555……9月的3级超纲了，判断题跟鬼一样……[:恐怖]\color{white}{555……9月的3级超纲了，判断题跟鬼一样……[:恐怖]}555……9月的3级超纲了，判断题跟鬼一样……[:恐怖]
希望下次4级不要也超纲……\color{white}{希望下次4级不要也超纲……}希望下次4级不要也超纲……
例1
上台阶
有NNN级的台阶，你一开始在底部，每次可以向上迈最多222级台阶（最少111级），问到达第NNN级台阶有多少种不同方式。
审题
一开始在第0层，每次要么跨1层，要么跨2层，利用加法原理：
* 到第1层有1种方法：跨1层；
* 到第2层有2种方法：一层一层走&直接跨两层；
这2个条件是我们预先知道的，后续的就很容易计算出来了。在走到第3层之前有2种情况，第一种情况我们是从第1层跨两层上来的，第二种情况我们是从第2层跨一层上来的。也就是说，求走到第3层的方式数就是求走到第1层和第2层的方式数之和。如果用aia_iai 记录走到第iii层的方式数，那么计算第3层方式数的算式就是：
a3=a1+a2a_3=a_1+a_2 a3 =a1 +a2
其实，也可以这样说：走到第3层的方式数是前两层的方式数之和。那么肯定不光第三层可以这样算，第4层和第5层应该也可以，第10层可以……这个楼梯的任意一层都可以这样算。如果想计算第nnn层呢？也是这个方法，第nnn层的方式数就是第n−1n-1n−1层和第n−2n-2n−2层的方式数之和。可以用以下算式表示：
an=an−1+an−2a_n=a_{n-1}+a_{n-2} an =an−1 +an−2
因为每一项都依赖它的前2项，所以算的时候要自底向上计算：从第3层开始一直这样算到第nnn层。看到这停一下，请先把上面的内容消化消化。
如果你完全理解了上面的内容，不难写出以下代码：
递推的基本思想
在上一题中，我们使用了一种新算法，这种算法叫做递推法，它的基本思想是利用已经计算出的结果来推导新的结果，从而避免重复计算，提高效率。递推法有正推和反推两种形式：
* 正推就是从前向后递推，已知小规模问题的解递推到大规模问题的解；
* 反推就是从后向前递推，已知大规模问题的解递推到小规模问题的解。
解决递推问题的步骤
解决递推问题的步骤如下：
1.定义初始状态
我们把递推过程中计算出的每一项称为一个状态，通常初始状态是题目中已经告诉我们的或是我们自己根据题干很容易推导出的一个量，后续的所有计算都是建立在初始状态的基础之上的。例如，在“上台阶”中，初始状态是第一层和第二层的方式数，这两个值是我们根据逻辑直接得到的，而不是用式子计算出来的。
找到了初始状态，再对它们进行定义。
2.找到递推关系式
要做好递推，这一步非常关键。递推关系式就是找出未知状态和已知状态之间的关系，并用一个宽泛的数学式子来表示这种关系。这个关系式应该对于任意一个状态都有效。
在例题1中，这种关系是“每一层的方式数就是前2层的方式数之和”，因此递推关系式就是an=an−1+an−2a_n=a_{n-1}+a_{n-2}an =an−1 +an−2 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例2
填数 在n个格子内填数，每个格子内只能填1,2,3中的一个，要求任意相邻的两个格子内的和为偶数，请你求出n个格子的时候有几种填法。
定义初始状态
先找初始状态，初始状态题目中的样例已经告诉我们了，即只有2个格子时的填法数。如果用aia_iai 来记录当有iii个格子时的填法数，那么a2=5a_2=5a2 =5。
找到递推关系式
在你找出了和为偶数的组合情况有1+3，3+1，1+1，3+3，2+2这5种以后，不难发现：如果前面的格子是填奇数，那么奇数后面还是奇数，有1或3这两种情况，则前nnn个格子的填法数是前n−1n-1n−1个格子的2倍。递推关系式为：
an=an−1×2a_n=a_{n-1}×2 an =an−1 ×2
如果考虑偶数情况（只有1种情况，因为2后面只能填2），那么乘以2之前要把偶数的一种情况去掉，乘完了以后再加上这一种情况。递推关系式：
an=(an−1−1)×2+1a_n=(a_{n-1}-1)×2+1 an =(an−1 −1)×2+1
完整代码
