加乘原理 与 简单递推

一、加乘原理

1. 加法原理

做一件事，完成它可以有 $n$ 类办法。第一类办法有 $m_1$ 种方法，第二类办法有 $m_2$ 种方法……第 $n$ 类办法有 $m_n$ 种方法，那么完成这件事共有

$$N = m_1 + m_2 + \cdots + m_n$$

种不同的方法。

每一类方法都可以独立完成任务。

2. 乘法原理

做一件事，完成它需要分成 $n$ 个步骤。第一步有 $m_1$ 种方法，第二步有 $m_2$ 种方法……第 $n$ 步有 $m_n$ 种方法，那么完成这件事共有

$$N = m_1 \times m_2 \times \cdots \times m_n$$

种不同的方法。

$n$ 个步骤都做了才可以完成任务。

二、简单递推

1. 递推算法的思想

递推算法是一种用若干步可重复运算来描述复杂问题的方法。通常是通过计算前面的一些项来得出序列中的指定项的值。

2. 递推算法的两个必要条件

• 递推关系式
• 递推边界

3. 解题方法总结

题目特征

• 方案数问题 / 问第 $n$ 项的方案数

解题步骤

1. 建数组，赋予数组意义

   • 递推问题数值增长很快，不清楚最后的数值大小，数组最好定义成 long long 类型。

2. 确定递推公式和初始值

   • 取其中第 $i$ 项，对最后 1 步的选法进行分类。先分类再分步，即可找到递推公式。
   • 根据递推公式，推出递推公式适用的第一种情况，前面的都需要手动给出初始状态。

3. 多组数据先打表，打表后再回答；一组数据直接推。

三、典型例题

三道题是同一个套路：站在最后一步去思考，最后一步是怎么走过来的。把最后一步可能的情况分完类，各类相加，就是递推式。

例题 1 走楼梯

题目

楼梯有 $n$ 个台阶，一次可以上一阶或两阶，求上到第 $n$ 阶的方法数。输入一个整数 $n$（$0 < n \le 50$），输出方法数。

样例

输入：
4
输出：
5

思路分析

站在最后一步去思考：走到第 $i$ 阶，最后一步是怎么上来的？

• 从第 $i-1$ 阶迈 1 阶上来；
• 从第 $i-2$ 阶迈 2 阶上来。

只有这两种情况，而且两者不会重复（最后一步迈的阶数不同），也不会遗漏。所以走到第 $i$ 阶的方法数，等于走到第 $i-1$ 阶的方法数加上走到第 $i-2$ 阶的方法数：

$$f[i] = f[i-1] + f[i-2]$$

递推式从 $i=3$ 起成立，前两项手动给出：$f[1]=1$（直接迈 1 阶），$f[2]=2$（1+1 或 2）。

核心代码

long long f[60]; //f[i]：上到第 i 级台阶的方案数
f[1] = 1; //初始值
f[2] = 2;
for(int i = 3; i <= n; i++){ //递推公式
	f[i] = f[i-1] + f[i-2];
}
//读入 n 后输出 f[n]

例题 2 蜜蜂路线

题目

蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行，求从蜂房 $a$ 爬到蜂房 $b$ 的路线数。第一行一个整数 $N$（$0 < N \le 100$）表示数据组数，后面 $N$ 行每行 $a$、$b$（$0 < a < b \le 50$），每组输出一行答案。

样例

输入：
2
1 2
3 6
输出：
1
3

思路分析

站在最后一步去思考：蜜蜂爬到终点，最后一步是从哪个蜂房爬过来的？

蜂房是六边形交错排列的，每个蜂房右边都紧贴着两个蜂房。把蜂房按图中顺序编号，从第 $i$ 号蜂房向右爬一步，只能到第 $i+1$ 号或第 $i+2$ 号蜂房；反过来看，能爬到第 $i$ 号蜂房的，只有第 $i-1$ 号和第 $i-2$ 号。

起点和终点也可以只看差值：从 $a$ 爬到 $b$，路线数只跟 $b-a$ 有关，跟具体的编号无关（把蜂房整体平移一下，图形是一样的）。记 $d=b-a$，走法数记作 $f[d]$。

于是最后一步只有两种情况：

• 从差值 $d-1$ 的那个蜂房爬一步过来；
• 从差值 $d-2$ 的那个蜂房爬一步过来。

两类不重不漏，加起来就是递推式：

$$f[d] = f[d-1] + f[d-2]$$

边界：$f[0]=1$（起点就是终点，不用爬也算一种路线）、$f[1]=1$（相邻，直接一步过去）。

题目有多组数据，先把 $d$ 从 2 到 49 的表一次性打出来，之后每组数据直接读表回答，不必每组重推。

核心代码

long long f[51]; //f[d] 终点和起点差值为d的方案数
f[0]=1; //初始值
f[1]=1;
for(int i=2;i<=49;i++){ //先打表
	f[i]=f[i-1]+f[i-2];
}
//之后每组数据读入 x、y，输出 f[y-x]

例题 3 走楼梯（一步 1、2、3 阶）

题目

楼梯有 $n$ 个台阶，一次可以上一阶、两阶或三阶，求上到第 $n$ 阶的方法数。输入一个整数 $n$（$0 < n \le 50$），输出方法数。

样例

输入：
4
输出：
7

思路分析

站在最后一步去思考：这次最后一步有三种走法，从第 $i-1$ 阶迈 1 阶、从第 $i-2$ 阶迈 2 阶、从第 $i-3$ 阶迈 3 阶上来，三种情况互不重复，加起来就是

$$f[i] = f[i-1] + f[i-2] + f[i-3]$$

递推式从 $i=4$ 起成立，前三项手动给出：$f[1]=1$、$f[2]=2$、$f[3]=4$。

和例题 1 对比一下：一步能迈的阶数多了一种，最后一步就多一类，递推式也跟着多一项。分类时把最后一步的所有可能都列出来，一项也别漏，这是解这类题的关键。

核心代码

long long f[60]; //f[i]：上到第 i 级台阶的方案数
f[1] = 1; //初始值
f[2] = 2;
f[3] = 4;
for(int i = 4; i <= n; i++){ //递推公式 可以上1阶 2阶 3阶
	//站在最后一步去思考 最后一步怎么走？ 三种情况考虑
	f[i] = f[i-1] + f[i-2] + f[i-3];
}
//读入 n 后输出 f[n]