数据结构算法每日一练（三）青蛙跳台阶

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果)。

（1）请用递归的方式求 n 级的台阶总共有多少种跳法: int jumpFloor(int n);

（2）给出此递归函数的时间复杂度。

解析：

当n = 0, jumpFloor(0) = 0;

当n = 1, jumpFloor(1) = 1;

当n = 2, jumpFloor(2) = 2;

当n > 3, jumpFloor(n) = jumpFloor(n - 1) + jumpFloor(n - 2);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int jumpFloor(int n) {
    if (n < 3)
        return n;
    else
        return jumpFloor(n - 1) + jumpFloor(n - 2);
}
int main() {
    int n;
    cin >> n;
    int res = jumpFloor(n);
    cout << res << endl;
    return 0;
}
时间复杂度为递归调用 $O(2^n)$

该题为斐波那契数列，分析方法与其一致。

斐波那契数列递推公式 $a_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n]$