27.跳台阶问题
题目:一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。
这道题最近经常出现，包括MicroStrategy等比较重视算法的公司
都曾先后选用过个这道题作为面试题或者笔试题。
斐波拉契数列的应用。
第一次跳1级，后面剩下的跳法为n-1级台阶的跳法，即f(n-1);
第一次跳2级，后面剩下的跳法为n-2级台阶的跳法，即f(n-2);
因此，n级台阶的跳法总是为f(n)=f(n-1)+f(n-2).
f(1)=1;
f(2)=2;
f(0)=1;
#include<iostream> using namespace std; int main(){ int fib[50]; fib[0]=fib[1]=1; int n; scanf("%d",&n); for(i=2;i<=n;i++) fib[i]=fib[i-1]+fib[i-2]; cout<<fib[n]<<endl; return 0; }
原文：http://www.cnblogs.com/wabi87547568/p/5272423.html