剑指Offer-9.变态跳台阶(C++/Java)

题目：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

假设我们要求跳上第3级的跳法，可以从第0级跳3级台阶到达，也可以从第1级跳2级台阶到达，还可以从第2级跳1级到达。

所以跳上第3级的跳法数等于到达第0级的跳数加上到达第1级的跳数再加上到达第2级的跳数，也就是f(3) = f(2) + f(1) + f(0)

可以推导出f(n) = f(n-1) + f(n-2) + ... + f(2) + f(1) + f(0)

我们还可以这样思考这个问题，从第0级跳到第n级需要经历n-1个台阶，因为青蛙可以跳1~n级青蛙跳上n级，青蛙跳法可以等价于台阶的选择，比如跳到3级时，青蛙先跳1级再跳两级，实际上就是青蛙从第0级先到达第1级台阶，再从第1级台阶跳到了第3级，而如果青蛙直接跳到了第3级，实际上就是没有使用台阶，所以青蛙的跳法等价于台阶的有无，跳到n级有n-1个台阶，每个台阶都存在使用或者不使用两个状态，所以最后的答案就是2^(n-1)，或者是1<<(n-1)。

程序：

C++

//dp
class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0) return 0;
        if(number == 1) return 1;
        vector<int> res(number+1, 0);
        res[0] = 1;
        res[1] = 1;
        for(int i = 2; i <= number; ++i){
            for(int j = 0; j < i; ++j)
                res[i] += res[j];
        }
        return res[number];
    } 
};

Java

public class Solution {
    public int JumpFloorII(int target) {
        return 1 << (target-1);
    }
}
/*import java.util.*;
public class Solution {
    public int JumpFloorII(int target) {
        return (int)Math.pow(2, target-1);
    }
}*/