【剑指offer】变态跳台阶

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
1、思路分析
是上一种跳台阶的变种。上一次主要是动态规划（迭代，项数确定）的思想，由于青蛙每次只能跳一步后者两步，因此当前台阶的跳法由前一级和前两级决定。而本题中，青蛙每一次可以跳的步数不再是完全一样的，而是由当前要跳的台阶数决定，因此这里没办法迭代或是用递归的思想。同时，由于每次有n种跳法，因此当前步数决定于前面每一级的跳法，即有：
f(n)=f(n-1)+f(n-2)+...+f(1)
f(n-1)=f(n-2)+...f(1)
得:f(n)=2*f(n-1)
2、代码

public class Solution {
    public int JumpFloorII(int target) {
        return (target < 0 ? 0 : 1 << (target-1));
    }
}

3、复杂度分析
待续