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

  • 思路：

    • f(1) = 1 // 跳上第一个台阶，只有一种可能；

    • f(2) = f(1) + 1 // 跳上第二个台阶，有两种可能, 从1台阶或0台阶跳上；

    • f(3) = f(2) + f(1) + 1 // 跳上第二个台阶，有3种可能, 从2台阶、1台阶或0台阶跳上；
      ...
      ...

    • f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1;

    • f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + 1;

    • f(n) = 2*f(n-1)

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

  return 2*JumpFloorII(target-1);
}
}

  • n台阶，只关心是最后一步从哪个台阶(preStep)直接跳到n台阶，如果题目有改变，青蛙依次可以跳1级台阶、2级台阶时，我们就只关心最后跳到n级台阶之前青蛙所在台阶，所以：f(n) = f(n-1) + f(n-2)

    public class Solution {
  public int JumpFloor(int target) {
      if(target <= 0) return -1;
      if(target == 1 || target == 2){
          return target;
      }

      return JumpFloor(target - 1) + JumpFloor(target - 2);
  }
}