（1）n个台阶，一次走1阶或2阶，问走n阶有多少可能？
（1<=n<=1000 000）结果用1000 0000 7取模输出。
输入格式：
输入台阶数n
输出格式：
结果用1000 0000 7取模输出。
输入样例：
3
输出样例：
3
#include <iostream>
using namespace std;
int f(int n) {
if(n == 1)
return 1;
if(n == 2)
return 2;
return f(n-1)+f(n-2);
}
int main() {
int n;
cin >> n;
int ans = f(n);
cout << ans;
return 0;
}
（1）算法的基本思想：
斐波那契数列。
举例子：
当阶数为1时，跳法：1种，记为F（1）=1
当阶数为2时，跳法：2种，记为F（2）=2
当阶数为3时，跳法：3种，记为F（3）=3
当阶数为4时，跳法：5种，记为F（4）=5
当阶数为5时，跳法：8种，记为F（5）=8
当阶数为6时，跳法：13种，记为F（6）=13
当阶数为7时，跳法：21种，记为F（7）=21
……
不难看出，F（n）=F（n-1）+F（n-2）
但是这种递归方案，在效率上可能并不是很高。递归过程中，有太多重复的元素被重新进行计算。
已下对此算法再进行改进：
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int f1=1;
int f2=2;
int fn;
if(n==1)
return f1;
else if(n==2)
return f2;
else for (int i = 2; i < n; ++i) {
fn = f1 + f2;
f1 = f2;
f2 = fn;
}
cout << fn;
return 0;
}
这种方法把已经得到的数列中间相保存起来，在下次需要计算的时候先查找一下，如果前面计算过就不用再重复计算了。
（3）一个台阶总共有 n 级，蛤有能力一次跳到 n 阶台阶，也可以一 次跳 n-1 阶台阶，也可以跳 n-2 阶台阶……也可以跳 1 阶台阶。
问蛤跳到 n 层台阶有多少种跳法？（n<=50）
输入格式：
输入台阶数
输出格式：
输出种类数
输入样例：
3
输出样例：
4
（1）算法的基本思想：
用 F(n)表示?跳上 n 阶台阶的跳法数
如果按照定义，Fib(0)肯定需要为 0，否则没有意义。
我们设定 F(0) = 1；n = 0 是特殊情况，通过下面的分析会知道，令 F(0) = 1 很有好处。
ps. F(0)等于几都不影响我们解题，但是会影响我们下面的分析理解。
当 n = 1 时， 只有一种跳法，即 1 阶跳：F(1) = 1;
当 n = 2 时， 有两种跳的方式，一阶跳和二阶跳：F(2) = 2; 到这里为止，和普通跳台阶是一样的。
当 n = 3 时，有三种跳的方式，第一次跳出一阶后，对应 F(3-1)种跳法； 第一次跳出二阶后，对应 F(3-2)种跳法；第一次跳出三阶后，只有这一种跳法。
F(3) = F(2) + F(1)+ 1 = F(2) + F(1) + F(0) = 4;
当 n = 4 时，有四种方式：第一次跳出一阶，对应 F(4-1)种跳法；第一次跳出二阶，对应 F(4-2)种跳法；第一次跳出三阶，对应 F(4-3)种跳法；第一次跳出四阶，只有一种跳法。
F(4) = F(4-1) + F(4-2) + F(4-3) + 1 = F(4-1) + F(4-2) + F(4-3) + F(4-4) 种跳法。
当 n = n 时，共有 n 种跳的方式：
第一次跳出一阶后，后面还有 F(n-1)中跳法；
..........................
第一次跳出 n 阶后，后面还有 F(n-n)中跳法。
F(n)=F(n-1)+F(n-2)+F(n-3)+..........+F(n-n) =F(0)+F(1)+F(2)+.......+F(n-1)。
通过上述分析，我们就得到了通项公式：
F(n) = F(0)+F(1)+F(2)+.......+ F(n-2) + F(n-1)
因此，有F(n-1)=F(0)+F(1)+F(2)+.......+F(n-2)
两式相减得：F(n)-F(n-1) = F(n-1)
F(n) = 2*F(n-1) n >= 3
这就是我们需要的递推公式：F(n) = 2*F(n-1) n >= 3
以上可以看出：
若阶数大于0的话，青蛙跳的方法有2的n-1次方种。
稍等一下：
还有一种更清奇的脑回路：
每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共用2^(n-1)种情况
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long long n;
cin >> n;
long long res;
if (n < 1)
res = 0;
else
{
res = pow(2, n - 1);
}
cout << res;
return 0;
}
