题目描述

一个楼梯共有n级台阶，每次可以走一级或者两级，问从第0级台阶走到第n级台阶一共有多少种方案。

输入格式
共一行，包含一个整数n。

输出格式
共一行，包含一个整数，表示方案数。

数据范围
1≤n≤15

样例

输入样例：
5
输出样例：
8

算法1 递归求解

基本解:
1. 阶梯为0， 方法1
2. 阶梯为1， 方法数1
3. 阶梯为2， 方法数2， 可以连续跳2次一级阶梯，或者跳1次二级
通解：
对于n(n>2)级台阶, 要写达到n阶台阶，每次跳1 或者 2
f(n) = f(n-1)+f(n-2)

时间复杂度

记不清啦哈-_-||

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int jumpN(int num)
{
    if (num == 0)
        return 0;
    else if (num == 1)
        return 1;
    else if (num == 2)
        return 2;
    else 
        return jumpN(num -1) + jumpN(num -2);
}

int main()
{
    int n ;
    cin >> n;
    cout << jumpN(n) <<endl;

    return 0;
}

算法2 递归+滚动变量

仔细观察我们会发现，递推时我们只需要记录前两项的值即可，没有必要记录所有值，所以我们可以用滚动变量递推。

时空分析

时间复杂度是 O(n) ，空间复杂度O(1)*

C++代码

    int jumpN(int number) {
    if (number <= 0)
        return 0;
    if (number == 1)
        return 1;
    else if (number == 2)
        return 2;

    int x = 1, y = 2;
    int z = 0;
    for (int i = 3; i <= number; i++)
    {
        z = x + y;
        x = y;
        y = z;
    }
    return z;
    }