第九题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：第一步跳1级，则剩下的有f(n-1)种跳法，
第一步跳2级，则剩下的有f(n-2)种跳法，
....
第一步跳n-1级，则剩下的有f(n-(n-1))=f(1)种跳法。
第一步跳n级，这也为1种跳法，即f(n-n)=f(0)=1种跳法。
所以，n级台阶的跳法f(n) = f(n-1)+f(n-2)+...+f(1)+f(0)。
同理，n-1级台阶的跳法f(n-1) = f(n-2)+f(n-3)+...+f(1)+f(0)。
所以，f(n)=2f(n-1)，f(n-1)=2f(n-2),...,f(2)=f(2-1)+f(2-2)=f(1)+f(0)=2f(1),f(1)=f(1-1)=f(0)=1。等比数列：
所以f(n) = 2^(n-1)。
Python：
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 2 ** (number - 1)
Java:
public class Solution {
public int JumpFloorII(int target) {
return (int)Math.pow(2, target-1);
}
}
