之前面试遇到了这种题目，不会，后来搜索了一下，感觉分析的很好

类型一

###青蛙跳一个N阶的台阶，每次可以跳1阶或者2阶，求跳完N阶y有多少种方法。 分析： N=1,f(N)=1 N=2,f(N)=2 N=3,f(N)=3 N=4,f(N)=5 可以发现 f(N)=f(N-1)+f(N-2) 由此也可以推想：比如要跳到第4阶楼梯上，那么青蛙的前置位置要么在第2阶、要么在第3阶，即f(4)=f(3)+f(2)，因此可以用递归或者循环求解

#类型二 ###一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 有类型1可知，f(N)=f(N-1)+f(N-2)+…+f(1) f(N-1)=f(N-2)+…+f(1) 所以f(N)=f(N-1)+f(N-1)=2f(N-1)= 22*f(N-2)=…=2^(N-1)*1 故运用公式就得结果。 在编程中 可以用一行来表示： return 1<<(N-1)；//左移N-1位