递推

例1

ACGO-上台阶

思路

一开始在第 $0$ 层，每次要么跨一层，要么跨两层，利用加法原理：

• 到第 $1$ 层有一种方法：跨一层；
• 到第 $2$ 层有两种方法：一层一层走&直接跨两层。

这两个条件是我们预先知道的，后续的就很容易计算出来了。在走到第 $3$ 层之前有两种情况，第一种情况我们是从第 $1$ 层跨两层上来的，第二种情况我们是从第 $2$ 层跨一层上来的。也就是说，求走到第 $3$ 层的方式数就是求走到第 $1$ 层和第 $2$ 层的方式数之和。如果用 $a_i$ 记录走到第 $i$ 层的方式数，那么计算第 $3$ 层方式数的算式就是：

$$a_3=a_1+a_2$$

如果是走到第 $i$ 层，那么方式数就是第 $i-1$ 层和第 $i-2$ 层的方式数之和。可以用以下算式表示：

$$a_{i}=a_{i-1}+a_{i-2}$$

因为每一项都依赖它的前 $2$ 项，所以算的时候要自底向上计算：从第 $3$ 层到第 $n$ 层依次计算每一项。看到这停一下，请先把上面的内容消化消化。

如果你完全理解了上面的内容，不难写出以下代码：

#include <iostream>
using namespace std;
int main() {
    int n;
    long long a[10005];
    cin >> n;
    a[1] = 1, a[2] = 2; // 预先知道的条件
    for (int i = 3; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2]; // 逐层计算每一层的方式数
    }
    cout << a[n];
    return 0;
}

递推的基本思想

在上一题中，我们使用了一种新算法，这种算法叫做递推法，它的基本思想是利用已经计算出的结果来推导新的结果，从而避免重复计算，提高效率。递推法有正推和反推两种形式：

• 正推就是从前向后递推，已知小规模问题的解递推到大规模问题的解；
• 反推就是从后向前递推，已知大规模问题的解递推到小规模问题的解。

解决递推问题的步骤

解决递推问题的步骤如下：

1.定义初始状态

我们把递推过程中计算出的每一项称为一个状态，通常初始状态是题目中已经告诉我们的或是我们自己根据题干很容易推导出的一个量，后续的所有计算都是建立在初始状态的基础之上的。例如，在“上台阶”中，初始状态是第一层和第二层的方式数，这两个值是我们根据逻辑直接得到的，而不是用式子计算出来的。

找到了初始状态，再对它们进行定义。

2.找到递推关系式

要做好递推，这一步非常关键。递推关系式就是找出未知状态和已知状态之间的关系，并用一个宽泛的数学式子来表示这种关系。这个关系式应该对于任意一个状态都有效。

在例题 $1$ 中，这种关系是“每一层的方式数就是前两层的方式数之和”，因此递推关系式就是 $a_i=a_{i-1}+a_{i-2}$。

例2

ACGO-填数

定义初始状态

先找初始状态，初始状态题目中的样例已经告诉我们了，即只有 $2$ 个格子时的填法数。如果用 $a_{i}$ 来记录当有 $i$ 个格子时的填法数，那么 $a_2=5$。

找到递推关系式

在你找出了和为偶数的组合情况有 $1+3,3+1,1+1,3+3,2+2$ 这 $5$ 种以后，不难发现：如果前面的格子是填奇数，那么奇数后面还是奇数，有 $1$ 或 $3$ 这两种情况，则前 $i$ 个格子的填法数是前 $i-1$ 个格子的 $2$ 倍。递推关系式为：

$$a_{i}=a_{i-1}×2$$

如果考虑偶数情况（只有 $1$ 种情况，因为 $2$ 后面只能填 $2$），那么乘以 $2$ 之前要把偶数的一种情况去掉，乘完了以后再加上这一种情况。递推关系式：

$$a_{i}=(a_{i-1}-1)×2+1$$

完整代码

#include <iostream>
using namespace std;
long long a[10005];
int main() {
    int n; 
    cin >> n;
    a[2] = 5; // 初始状态
    for (int i = 3; i <= n; i++) {
        a[i] = (a[i - 1] - 1) * 2 + 1; // 递推关系式
    }
    cout << a[n];
    return 0;
}

例3

ACGO-Gold King上色

定义初始状态

题目说了，$1$ 个格子和 $0$ 个格子的填法数都为 $0$，但这道题光有这两个条件还不够。顺着往下想，当有 $2$ 个格子时，第 $1$ 格就是头，第 $2$ 格就是尾，根据题意，这两个格子的颜色应该互不相同。从三种颜色中选两种颜色组合在一起，有红绿、红黄、绿红、绿黄、黄红、黄绿六种方案。用 $a_{i}$ 表示有 $i$ 个格子时的填法数，则 $a_0=0,a_1=0,a_2=6$。

找到递推关系式

当有 $3$ 个格子时，第 $1$ 个格子是头，第 $3$ 个格子是尾，第 $3$ 个格子既不能和第 $1$ 个格子相同，也不能和与它相邻的第 $2$ 个格子相同，那第 $3$ 个格子只有除去前两个格子的剩下的一种颜色可填。所以 $2$ 个格子的填法数是 $6$，$3$ 个格子的填法数也是 $6$。

当有 $4$ 个格子时，要考虑 $2$ 种情况。第一种情况，是直接在符合要求的三个格子之后加上一个格子。第 $1$ 个格子是头，第 $4$ 个格子是尾，第 $4$ 个格子既不能和第 $1$ 个格子相同，也不能和与它相邻的第 $3$ 个格子相同，那第 $4$ 个格子只有除去第 $1$ 个格子和第 $3$ 个格子的剩下一种颜色可填，则 $4$ 个格子的填法数和 $3$ 个格子一样，也是 $6$。关系式为：

$$a_{i} = a_{i-1}$$

第二种情况，因为增加到 $4$ 格后，第 $3$ 格已经不是尾了，可以和第 $1$ 格相同。第 $4$ 个格子仍然既不能和第 $1$ 个格子相同，也不能和与它相邻的第 $3$ 个格子相同，但第 $1$ 格和第 $3$ 格实际上是同一种颜色，所以第 $4$ 格可以填除去这一种颜色的其余两种颜色。而第 $1$ 格确定了，第 $3$ 格就不用考虑了，全部 $4$ 格的填法数只跟去掉第 $3$ 格的前 $2$ 格有关，并且是前 $2$ 格填法数的 $2$ 倍。关系式为：

$$a_{i}=a_{i-2}×2$$

最终的填法数就是这两种情况的填法数之和，递推关系式：

$$a_{i}=a_{i-1}+a_{i-2}×2$$

完整代码

#include <iostream>
using namespace std;
long long a[60];
int main() {
    a[0] = 0, a[1] = 0, a[2] = 6;
    int n;
    cin >> n;
    for (int i = 3; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2] * 2;
    }
    cout << a[n];
    return 0;
}