这个算法递推1是如何实现的递推机制？

递推 1 引入 我们常常说的斐波那契数列大家肯定知道，一开始学 OI 时大多数人都是用循环来解决的（c = a + b, a = b, b = c）。但你有没有想过一点，如果再复杂一点，那么代码会很难写。下面就介绍一种算法——递推。 概念 递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。无论顺推还是逆推，其关键是要找到递推式。这种算法能使复杂运算化为若干步重复的简单运算。 分析 我们就拿最典型的斐波那契数列来说，它的公式为 \(\begin{cases}\text{if}\ 1 \le i \le 2 & f_i = 1 \\ \text{if}\ i \ge 3 & f_i = f_{i - 1} + f_{i - 2}\end{cases}\)（推理过程），如果我们要求斐波那契数列的第 \(n\) 项，那该怎么办？ 我们先建立一个 \(f\) 数组，把 \(f_0, f_1\) 的初始值赋值为 \(1\)。然后跑 for 循环遍历 \(2 \sim n\)，对于每个 \(i\) 都要进行一次递推（f[i] = f[i - 1] + f[i - 2]）。 代码如下： f[0] = f[1] = 1; for (int i = 2; i <= n; ++ i) { f[i] = f[i - 1] + f[i - 2]; } 递推其实就是数组 + 循环，只要推出了递推式，什么都好办了。 例题 1 有 \(N\) 级台阶，你一开始在底部，每次可以向上迈 \(1\sim K\) 级台阶，问到达第 \(N\) 级台阶有多少种不同方式 （\(\bmod 100003\)）。（\(1\leq N\leq100000\)，\(1\leq K\leq100\)） 我们发现，第 \(i\) 级台阶可以从 \(i - 1, i - 2, \cdots, i - K\) 级台阶迈上来。当 \(K = 2\) 时，是不是就是斐波那契数列？没错，这题是斐波那契数列进阶版。 我们先赋初始值（\(f_0 = f_1 = 1\)），第一层循环跟普通斐波那契一样，第二层套一个 \(1 \sim K\) 的循环（因为第 \(i\) 级台阶可以从 \(i - 1, i - 2, \cdots, i - K\) 级台阶迈上来），如果 \(j \le i\)，那么 \(f_i\) 就为 \(f_i + f_{i - j}\)（原理跟普通斐波那契一样），注意取模。 代码： f[0] = f[1] = 1; for (int i = 2; i <= n; ++ i) { for (int j = 1; j <= k; ++ j) { if (j <= i) { f[i] = (f[i] + f[i - j]) % kMod; // 注意取模，kMod 是模数（100003） } } } f[n] %= kMod; // 注意取模 cout << f[n] << '\n'; 例题 2 派蒙给了你两个数 \(n, x\)，\(x\) 初始值为 \(1\)，还给了你两种操作：1. \(x \gets 2x\)（把 \(x\) 变为 \(2x\)（相当于 \(2 \times x\)））。2. \(x \gets x + 1\)（把 \(x\) 变为 \(x + 1\)）。现在派蒙想知道至少花多少步才能把 \(x\) 变成 \(n\)。（\(1 \le n \le 10^5\)） 我们可以发现数字 \(P\) 可以从 \(\cfrac{P}{2}\) 和 \(P - 1\) 得来，所以得到递推式 \(f_i = \min(f_{i - 1} + 1, f_{i \div 2} + 1)\)。但这个递推式只对于偶数 \(i\)，我们发现，如果 \(P \bmod 2 = 0\)，那么把 \(P\) 变成 \(P + 1\) 需要 \(1\) 步 (\(x \gets x + 1\)）。所以对于每个奇数 \(i\)，有 \(f_i = f_{i - 1} + 1\)。