递推算法

什么是递推算法

递推算法，是一种从已知条件出发，依据某种递推关系，逐步推出所要求的结果的一种算法。

递推算法避开了求通项公式的麻烦，把一个复杂问题的求解，分解成一系列较小的、相互关联的子问题。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。

递推、递归、动态规划（DP）这三者相互都有关联，也有区别，很多同学在学习的时候都弄得云里雾里，我们在后面讲完动态规划后再反过来看就会很清楚了。

前面我们已学过递归，递推算法与递归算法有所不同，递推是通过迭代的方式进行计算，而递归是通过函数自身调用来实现。

下面通过一个大家可能已经比较熟悉的例子：求 Fibonacci 数列第 n 项 ，用递推和递归两种方式来对比实现，来帮助我们更好的理解什么是递推。

递归算法实现求和：

#include <iostream>
using namespace std;

int fib(int n) {
  if (n == 0) return 0;
  else if (n == 1) return 1;
  else return fib(n - 1) + fib(n - 2);
}

int main() {
    int n;
    cin >> n;

    cout << fib(n) << endl;

    return 0;
}

递推算法实现求和：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int fib[100];
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }

    cout << fib[n] << endl;

    return 0;
}

需要注意的是，尽管我们习惯是从第 1 项开始来说的，但斐波那契数列（Fibonacci）的定义是有第零项的，第零项的值是 0。

对比一下递归与递推两种算法的实现，可以看到，递归是从未知到已知，一步一步倒着推回去，求解是通过函数调用自身来实现的。

假设我们有这样一个函数 f(n) 是求斐波那契数列第 n 项的，根据公式 f(n) = f(n - 1) + f(n - 2)，要求 f(n)，只需要知道 f(n - 1) 和 f(n - 2) 就可以了，从后往前，依次倒推，直到 f(0) 和 f(1)，而这两个函数的值是已知的，再从已知到未知，最终求出 f(n)。

如下图所示，先是从未知到已知（从上到下推导），然后是从已知到未知（从下往上求值）。

而对于递推来说，是从已知条件到未知，一步一步往前推，最终得出结果，整个求解是通过迭代（借助数组和循环）来实现的。

f[1] = 1 和 f[2] = 1，这是已知最简单的两个条件，有了前两项，第 3 项就可以求出来了，有了第 2 项和第 3 项，第 4 项也可以求出来了，一直往下，最终到求出 f[n]。

递推更符合人的推理过程，和数学中的归纳法一致，从已知到未知去求解；

递归更符合计算机处理问题的思路，把所求问题划分成若干比较简单的子问题，分别处理这些子问题，处理完成后，再把这些子问题的结果进行合并，最终得出答案。

利用递推算法求解相关问题，有两个关键点：

找到相邻项的递推关系，得出递推公式
递推的初始值，有了初始值，根据递推公式就可以一步一步迭代下去了

上面是用数组来实现递推算法的，当然也可以不用数组，在求 Fibonacci 数列的递推公式中，当前项的值只与它前面两项的值相关，因为在同一时间，我们只关系三个值（当前项，前一项，再前一项），因此我们可以用三个变量来实现递推，一轮一轮往前迭代就可以了。

下面的代码是用变量迭代的方式来实现的递推算法。

#include <iostream>
using namespace std;

int main() {
  int n, x, y, z;
  cin >> n;
  x = 0;
  y = 1;

  if (n == 0) z = 0;
  if (n == 1) z = 1;

  for (int i = 2; i <= n; i++) {
    z = x + y;
    x = y;
    y = z;
  }

  cout << z << endl;
  return 0;
}

这种通过变量迭代实现的递推算法从理解上来说没有通过数组实现那么直观，但节约了使用数组需要的额外存储空间，各有优劣。

再来看一个很简单的例子，从外部输入一个整数 $n$ ，编程求 $1+2+3+...+n$ 的和。

在讲解循环的时候专门有讲过，通过循环累加求和就可以完成，参考代码如下：

#include <iostream>
using namespace std;

int main() {
  int n, sum = 0;
  cin >> n;

  for (int i = 1; i <= n; i++) {
    sum = sum + i;
  }

  cout << sum << endl;

  return 0;
}

之所以叫累加求和，就是一个一个累加到 sum 去中，也很好理解。

下面我们转换一下，刻意用递推算法来求解这个问题。

递推算法求和（数组版本）

#include <iostream>
using namespace std;

int main() {
  int n, q[1000];
  cin >> n;

  q[1] = 1;
  for (int i = 2; i <= n; i++) {
    q[i] = i + q[i - 1];
  }

  cout << q[n] << endl;
  return 0;
}

递推算法求和（非数组版本）

#include <iostream>
using namespace std;

int main() {
  int n, x, y;
  cin >> n;

  x = 1;

  for (int i = 2; i <= n; i++) {
    y = x + i;
    x = y;
  }

  cout << y << endl;
  return 0;
}

当然，在实际应用中，使用传统的累加求和方法更加容易理解，这里特别用递推的方式来求和，主要是方便大家更好的理解递推的核心思想。

递推求解步骤

通过上面两个大家已经比较熟悉的两个例子，相应大家已经知道，用递推算法求解问题的基本步骤：

第一步：初始条件设置。这是递推的起始点，没有初始条件，整个递推就没办法开始。
第二步：利用递推迭代求解。也就是通过观察去得出递推公式，然后以初始条件为起始点，依据递推公式一步一步去向前迭代求解。
第三步：根据题目条件，按格式对结果进行输出。

在三个步骤中，如何得出递推公式非常关系，难点也在这儿，大家只能在理解的基础之上，通过做练习，多总结，增强自己在这一块的能力。

练习: 上台阶

题目描述

楼梯有 $n (0 \lt n \lt 71)$ 阶台阶，上楼时可以一步上 1 阶,也可以一步上 2 阶,也可以一步上 3 阶，编程计算要上到第 n 级台阶，共有多少种不同的走法。

输入描述

输入一个整数 $n$ ，表示第 $n$ 级台阶

输出描述

输出一个整数，代表到达第 $n$ 级台阶的走法数量

输入输出样例

输入数据 1

输出数据1

输入数据2

输出数据2

题目解析

小时候大家估计都见过爬台阶这个题，只是台阶数往往较少。比如说，如果楼梯有 4 级台阶，规定一步只能上一级或上两级，请问要走上这个台阶共有多少种不同的走法？

在小学阶段，我们通过枚举，在保证不重复、不遗漏的前提下，把所有情况罗列出来就可以完成了，那个时候更多是锻炼一种有序思考的基础能力。

但如果台阶一旦较多，就像上面这个题目一样，要通过人力枚举去完成几乎是不太可能了。

我们需要想更「聪明」一点的办法，如果仔细观察，我们可以得出一个规律，从第三级台阶之后，要跳到任意第 n 级台阶，只可能有下面三种情况：

从第 n-1 级，跳一级上来；
从第 n-2 级，跳两级上来；
从第 n-3 级，跳三级上来；

我们可以归纳出下面这样的一个数学公式：

f(n) = f(n-1) + f(n-2) + f(n-3)

这里的 $f(n)$ 表示如果有 $n$ 级台阶，共有的走法总数。

实际上，得出的这个公式就是我们的递推公式，我们只需要再找出递推的初始条件即可。

对于本题来说，当前状态（到第 $n$ 级的不同走法）依赖于前面三项（第 $n-1$ 级、第 $n-2$ 级与第 $n-3$ 级的不同走法），因此容易想到，要实现递推，我们只需要知道：

$f(1)$ ，只有一级台阶时的不同走法
$f(2)$ ，只有两级台阶时的不同走法
$f(3)$ ，只有三级台阶时的不同走法

实现代码

// 上台阶，递推算法
// 求到第 n 级台阶总共的走法有多少种
#include <iostream>
using namespace std;

const int N = 75;

// 这里用 long long 类型，主要是走法的量很可能会特别大
long long f[100];

int main() {
    int n;
    cin >> n;

    // 注意，这里就不考虑 0 级了，不存在 0 级
    f[1] = 1; // 到第 1 级只 1 种走法
    f[2] = 2; // 到第 2 级有 2 种走法
    f[3] = 4; // 到第 3 级有 4 种走法

    for (int i = 4; i <= n; i++) {
      f[i] = f[i-1] + f[i-2] + f[i-3];
    }

    cout << f[n] << endl;

    return 0;
}

练习: 分糖果

题目描述

妈妈给小明买了若干糖，他把糖分给大家吃。第 1 次分了其中一半多 1 颗出去；第 2 次又分了剩下的一半多 1 颗出去；依次这样，每次都分剩下的一半多 1 颗出去，当准备分第 $n$ 次时，小明手上只剩下 1 颗糖了，请问妈妈当时给小明买的糖总共有多少颗呢？

输入描述

输入一个正整数 $n(1\le n \le 10)$ ，代表准备分第 $n$ 次时，手上只剩下 1 颗糖了

输出描述

输出一个整数，代表当时妈妈给小明买的糖的总颗数

输入输出样例

输入数据 1

输出数据 1

输入数据2

输出数据2

题目解析

当小明准备分第 $n$ 次时，手上只剩下 1 颗糖了，因此我们可以倒着来想这个问题。

如果手上有 $n$ 颗糖，第一次分了一半多 1 颗出去，也就是手上只剩下 $\frac{n}{2} -1$ 颗，倒过来，如果当前手上有 $i$ 颗糖，那在最后一次分之前手上就应该有 $2 \times (i + 1)$ 颗糖。

举个例，最后一次准备分时，只剩下 1 颗糖，那倒数第 2 次准备分时，小明手上应该有 $2 \times (1 + 1)$ ，也就是 4 颗糖。

可以验证一下，4 颗糖分一半还多 1 颗，就只剩下 1 颗糖了，验证通过。

有了这个递推规律，剩下的就是代码实现的问题了。

代码实现

3ze4uqbdu - C++ - OneCompiler

#include <iostream>
using namespace std;

const int N = 12;
int candies[N];

int main() {
  int n;
  cin >> n;

  candies[1] = 1; // 递推初始值

  for (int i = 2; i <= n; i++) {
    candies[i] = 2 * (candies[i - 1] + 1); // 递推公式
  }

  cout << candies[n] << endl;
  return 0;
}

练习: 昆虫繁殖

来源：一本通，T1312，昆虫繁殖

题目描述

科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过 $x$ 个月产 $y$ 对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵（过 $x$ 个月产卵），问过 $z$ 个月以后，共有成虫多少对？ $0 \le x \le 20$ ， $1 \le y \le 20$ , $x \le z \le 50$ 。

输入

$x, y, z$ 的数值。

输出

过 $z$ 个月以后，共有成虫对数。

输入数据1

1 2 8

输出数据1

题目分析

这也是一个典型的递推题目，用递推算法求解问题时，最难也是最关键的一步是找到递推式。

假设第 i 月的成虫数量表示为 a[i]，卵数量表示为 b[i]。根据题意，对于第 n 月的成虫数量，后我们可以有下面的结论与递推关系。

第一个月只有一对成虫，因此在最初的 x 个月内，成虫一直都只有一对，而且没有卵
a[n] = a[n - 1] + b[n - 2]，因为两月前的卵现在都变为成虫了
b[n - 2] = a[n - 2 - x] * y，n - 2 月的卵全部来自为这个月往前推 $x$ 个月的成虫产的卵。

有了这个递推关系，代码都比较好写了。

需要注意的是，题目是问第 $z$ 个月后有成虫多少对，因此实际上求的是 $z + 1$ 个月时的成虫数量！

代码实现

// 一本通，T1312，昆虫繁殖
#include <iostream>
using namespace std;

long long a[60], b[60];

int main() {
  int x, y, z;
  cin >> x >> y >> z;

  // 前 x 个月内无产卵，成虫数量也没变化
  for (int i = 1; i <= x; i++) {
    a[i] = 1;
    b[i] = 0;
  }

  for (int i = x + 1; i <= z + 1; i++) {
    b[i] = a[i - x] * y; // 当前月的卵来自于 x 个月前的成虫产的卵
    a[i]= a[i - 1] + b[i - 2]; // 当前月的成虫来自上个月的成虫以及上上个月的卵长成的成虫
  }

  cout << a[z + 1] << endl; // 输出第 Z 个月后的成虫数量

  return 0;
}

练习: 位数问题

来源：一本通，T1313，位数问题

代码地址：3z2s3ptf8 - C++ - OneCompiler

题目描述

在所有的 N 位数中，有多少个数中有偶数个数字 3 ？由于结果可能很大，你只需输出这个答案对 12345 取余的值。

输入

读入一个数 N（ $N \le 1000$ ）。

输出

输出有多少个数中有偶数个数字 3。

输入输出样例

输入

输出

题目分析

先看最简单的情况：

只有一位数
- 含奇数个 3，就只有 3 这一种可能
- 含有偶数个 3，共有 9 种可能，除开 3 的所有数字，0,1,2,4,5,6,7,8,9 都是
如果是两位数

可以看成两个一位数的组合，也分两种情况
- 含有偶数个3
  
  a. 奇｜奇，只有 3 | 3 这一种情况
  
  b. 偶 | 偶，高位有 9 种可能，低位也有 9 种可能，共 81 种可能
- 含有奇数个3
  
  a. 奇 | 偶，共有 1 × 9 种可能
  
  b. 偶 | 奇，共有 9 × 1 种可能
如果有 n 位

可以看成最高位加上 n - 1
- 含有偶数个 3 。even[n] = 9 × even[n-1] + 1 × odd[n-1] 。
  
  a. 偶｜剩下的其它偶。
  
  b. 奇 | 剩下的其它位奇。
- 含有奇数个 3 。odd[n] = 1 × even[n-1] + 9 × odd[n-1] 。
  
  a. 奇 | 剩下的其它偶。
  
  b. 偶 | 剩下的其它奇。

代码实现

// 一本通，T1313，位数问题
#include <iostream>
using namespace std;

const int LEN = 1010;
const int MOD = 12345;
int even[LEN], odd[LEN];

int main() {
    int n, k = 9;
    cin >> n;

    even[1] = k; // 一位数，含偶数个 3 共有 9 种可能
    odd[1] = 1; // 一位数，含奇数个 3 只有一种可能

    for (int i = 2; i <= n; i++) {
      if (i == n) k--; // 最高位为 0 时，在前面一位已经计算了，去掉

      even[i] = (k * even[i - 1] + 1 * odd[i - 1]) % MOD;
      odd[i] = (1 * even[i - 1] + k * odd[i - 1]) % MOD;
    }

    cout << even[n] << endl;

    return 0;
}

练习: 过河卒（Noip 2002）

一本通，T1314，过河卒

代码地址：3z2s9mj79 - C++ - OneCompiler

题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。

卒行走的规则：可以向下或者向右。同时，在棋盘上的某一点有一个对方的马（如 C 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。如图3-1中的 C 点和 P1、P2、P3、P4、P5、P6、P7、P8，卒不能通过对方马的控制点。

棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)（n,m 为不超过 20 的整数）。同样，马的位置坐标也是需要给出的，C ≠ A 且 C ≠ B。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入

给出n、m 和 C 点的坐标。

输出

从 A 点能够到达 B 点的路径的条数。

输入输出样例

输入

8 6 0 4

输出

题目分析

（待补充）

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n, m;
int x, y;

long long q[N][N]; // 到 i, j 这个点的路径数量
bool st[N][N]; // 默认为 false，表示能走。true 表示不能走

const int ctr[8][2] = {
  {2, 1}, // P1
  {1, 2}, // P2
  {-1, 2}, // P3
  {-2, 1}, // P4
  {-2, -1}, // P5
  {-1, -2}, // P6
  {1, -2}, // P7
  {2, -1} // P8
};

int main() {
  cin >> n >> m >> x >> y;

  st[x][y] = true;

  // 将 8 个控制点进行标记
  for (int i = 0; i < 8; i++) {
    int tx = x + ctr[i][0];
    int ty = y + ctr[i][1];

    if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) {
      st[tx][ty] = true;
    }
  }

  q[0][0] = 1; // A 点不会被封，递推的起始条件

  // 遍历整个棋盘，计算路径数量
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      if (st[i][j]) continue;
      if (i > 0) q[i][j] += q[i - 1][j];
      if (j > 0) q[i][j] += q[i][j - 1];
    }
  }

  cout << q[n][m] << endl;

  return 0;
}

总结

递推算法就是一种通过递推关系，一步一步从已知条件往下推进，最终解决未知问题的算法。递推算法通常具有简单、高效的特点，适用于解决具有明显递推规律的问题。有些问题看似复杂，一旦找到递推关系，用编程来解决其实是比较容易的。