一、引言

还是稚嫩的时候，我们也许都听到或者看到过这么一道题：

有 10 个台阶，你一次能走 1 个或者 2 个台阶，那么请问，走完这 10 个台阶共有几种方式？

又或者这道题改个方式问：

有一只青蛙，它尝试跳上有 n 个台阶的楼梯，它一次能够跳 1 阶或者 2 阶，那么请问，它跳上这 n 个台阶共有几种方式？

其实，题目的问法有千千万万种，但是题目的核心都没有变。

二、让我们来解决引言的问题

这个问题的解法呢，让我们来做个统计：

台阶数（n）方式（最大2阶）1122334558613721834955

我们可以自己算算前几个方式的可能性，然后呢，让我们来看看有什么规律。

发现了什么了吗？我们发现，第 2 个数之后的数的方式值都是前 2 个方式值之和。

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

这也就是著名的斐波那契数列。

了解了规律之后，让我们来编写代码：

int fibonacci(int n) { if (n == 1) return 1; if (n == 2) return 2; return fibonacci(n - 1) + fibonacci(n - 2); }

这段代码很简单，使用了简单的迭代，先计算 n == 1 和 n == 2 的情况，再计算普通情况的值，代码也非常简练。

三、但是总会有人一步可以走 3 个台阶啊

有人会想，那要是这个人可以一步走 3 步怎么算呢？或者我们扩展下，这个人可以走 m 步：

假想有个人，他要走完 n 阶的台阶，他一步可以走 m 步，但是 m 绝对小于 n，此时他走完 n 阶的台阶有多少种方式呢？

看到这里，你也许不想走楼梯了，咱们坐电梯不好吗？

好了，其实这里我也思考了很久，让我们来观察下走 3 步的情况下是什么情况：

台阶数（n）方式（最大3阶）112234475136247448819149

能看出什么规律来吗？

其实要是对刚才的例子有点印象，这里的规律不难看出。

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

那么让我们推想下，当一次可以走 m 阶，那么前面就会有 m 个常量，后面就是 m 个前面方式量的和，是这样的吧，没错。

那么让我们编写一个函数的话，我们需要计算前面 m 个常量的值啊。这样很简单，我们看看这些值的特征，满足 2 的 n - 1 次幂的特征，于是逻辑如下：

f(n) = 2^{n - 1} f(n) = f(n - 1) + f(n - 2) + f(n - 3);

既然公式弄清楚了，就让我们开始编码吧：

#include <iostream> #include <cstdlib> #include <cmath> class Solution { public: int wildFibonacci(int count, const int m) { // 前 m 个数是 2 的 count 幂次数 if (count < m) return pow(2, count); int num = 0; // 后面的数是 前 m 个 wildFibonacci 数之和 for (int i = 1; i <= m; ++i) num += wildFibonacci(count - i, m); return num; } int countPaths(int n, int m) { // n 个值，有 0 ~ n - 1的取值范围 return wildFibonacci(n-1, m); } }; int main() { Solution solution; int n = 0; int m = 0; std::cin >> n >> m; std::cout << "Total paths is " << solution.countPaths(n, m) << std::endl; system("pause"); return 0; }

三、总结

编码很简单，但是公式得出很难。

可以说认识到了算法的重要性，作为程序员，还是需要有相当的数学思维的，正打算重学算法，希望能够坚持下来。