剑指offer-贪心跳台阶

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

思路
跳n级台阶=
第一次跳n(1)+
第一次跳n-1，剩下跳1级(1)+
第一次跳n-2，剩下跳2级(2)+
第一次跳n-3，剩下跳3级(4)+
...
第一次跳3，剩下跳n-3级+
第一次跳2，剩下跳n-2级+
第一次跳1，剩下跳n-1级

f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)
f(n-1) = f(n-2) + ... + f(1) + f(0)
=> f(n) = 2f(n-1)

Java

public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 2) {
          return target;
        }
        return JumpFloorII(target-1)*2;
    }
}

不使用递归

public class Solution {
  public int JumpFloorII(int target) {
    if (target <= 2) {
      return target;
    }
    int sum = 2;
    for (int i = 3; i <= target; i++) {
      sum = 2*sum;
      
    }
    return sum;
  }
}