题目描述
一个楼梯共有 nn 级台阶,每次可以走一级或者两级,问从第0级台阶走到第n级台阶一共有多少种方案。
样例
输入样例:
5
输出样例:
8
C++ 代码
#include <iostream>
using namespace std;
int jump(int n)
{
if (n <= 2) return n;
return jump(n - 1) + jump(n - 2);
}
int main()
{
int n;
cin >> n;
cout << jump(n) << endl;
return 0;
}
你可以再讲个递推的$O(n)$,甚至还可以写矩阵乘法$O(2^3 \log _ 2 n)$