第九题：一只青蛙一次可以跳上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);
    }
}