变态跳台阶多种解法

• 普通人能想到的暴力解法：
  跳上第n个台阶，我们可以推算上一步是如何跳到这第n个台阶的：

  • 如果上一步跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]

  • 如果上一步跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]

  • 如果上一步跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0]

那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + ... + f[0]
显然初始条件f[0] = f[1] = 1
所以我们就可以先求f[2]，然后f[3]...f[n-1]， 最后f[n]

public class Solution {
    public int JumpFloorII(int target) {
        if(target == 0 || target == 1)
            return 1;
        int[] f = new int[target+1];
        f[0] = f[1] = 1;
        for(int i = 2; i <= target; i++){
            for(int j = 0; j < i; j++){
                f[i] += f[j];
            }
        }
        return f[target];
    }
}

时间复杂度 O(N2)
空间复杂度 O(N)

• 我们可以发现规律
  f(1) = f(0) = 1;
  f(2) = f(1) + f(0) = 2 * f(1);
  f(3) = f(2) + f(1) + f(0) = 2 * f(2);
  f(4) = 2* f(3)
  ...
  f(n) = 2 * f(n-1)
  因为初始f(1)为1，所以刚好可以利用位运算。

  public class Solution {
    public int JumpFloorII(int target) {
        return 1 << (target - 1);    //左移1位是乘2，左移几就是几次乘2
    }
  }

时间复杂度 O(1)
空间复杂度 O(1)


基于该思想还有别的方法能够降低复杂度

public class Solution {
    public int JumpFloorII(int target) {
        if(target == 0 || target == 1)
            return 1;
        int a = 1, b = 0;
        for(int i = 2; i <= target; i++){
            b = a << 1;
            a = b;
        }
        return b;
    }
}

时间复杂度 O(n)
空间复杂度 O(1)


只有1级和2级台阶的解法：

可以使用递归：

public class Solution {
    public int JumpFloor(int target) {
        if(target == 1)
               return 1;
        if(target == 2)
               return 2;
        return JumpFloor(target-1) + JumpFloor(target-2);

    }
}

但是时间复杂度为 O(2的n次方)


因此在面试时还是推荐递推型：

public class Solution {
    public int JumpFloor(int target) {
        int a = 1, b = 1;
        for(int i = 1; i < target; i++){
            //a是n后返1个的台阶
            a = a + b;
            //b是n后返2个的台阶
            b = a - b;
        }
        return a;

    }
}