剑指 Offer - 09 - 变态跳台阶

Question

题目

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

解析

这题不同于跳台阶问题的地方在于， n 层可以由前面的任意一层跳过来：

• 第 n 个台阶可以由前面所有的台阶跳过来即 f[n] = f[n-1] + f[n-2] + ... f[1]；
• 然后加上直接跳到自己这个台阶(+1)；

1、递归

public class Solution {

    public int JumpFloorII(int target) {
        if (target < 1)
            return 0;
        if (target == 1 || target == 2)
            return target;
        int sum = 1; //加上自己一步直接跳到自己的台阶
        for (int i = 1; i < target; i++)
            sum += JumpFloorII(i);
        return sum;
    }
}

2、递推(DP)

public class Solution {
    public int JumpFloorII(int target) {
        if (target < 1)
            return 0;
        if (target == 1 || target == 2)
            return target;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            dp[i] = 0;
            for (int j = 1; j < i; j++) //前面的和
                dp[i] += dp[j];
            dp[i] += 1;//加上自己的
        }
        return dp[target];
    }
}

稍微优化一下:

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

3、滚动优化

public class Solution {
    public int JumpFloorII(int target) {
        if (target < 1)
            return 0;
        if (target == 1 || target == 2)
            return target;
        int preSum = 3, res = 0;//一开始  preSum = f1 + f2 的值
        for (int i = 3; i <= target; i++) {
            res = preSum + 1;  //之前的和　加上自己的
            preSum += res;
        }
        return res;
    }
}

4、规律

推出前面几项也可以看出其实就是一个等比数列求和 ，也就是 2^n-1。

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

    public int JumpFloorII(int target) {
        return 1 << (target - 1);
    }
}