每天一道算法题——变态跳台阶

每天一道算法题——变态跳台阶 2022-05-28 477

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。测试用例: 0 1 2 3 4 … 10 对应输出应该为: 0 1 2 4 8 … 512

分析：这里有两种分析方法，第二种一定会惊艳到你的。

根据上述测试用例及结果，差不多已经可以看出来一些规律了。但是这里再进行一细节方面的分析： f(1) = 1 f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。 f(3) = f(3-1) + f(3-2) + f(3-3) … f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n) 由上述可推导出： f(n-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) + f(n-1) = f(n-1) + f(n-1) 则可以得出最终结论,在n阶台阶，一次有1、2、…n阶的跳的方式时，总得跳法为： | 0 ,(n=0 ) f(n) = | 1 ,(n=1 ) | 2*f(n-1),(n>=2) 以上，可以看出，若台阶大于0的话，青蛙跳的方法共有2(n-1)种。
但网络上有网友提出了另外一种更加有效地分析：每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共用2^(n-1)中情况不得不说，这个思路实在实在是精辟。

源码：

public class Test1 {
    public int JumpFloorII(int target) {
        if (target<1) {
            return 0;
        }else {
            return (int) Math.pow(2, target-1);
        }
    }
}

2^(n-1)也可以用左移操作进行。

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

但是这样代码会比较不容易阅读，而且Java的Pow函数底层也是调用的native方法，速度和内存占用和左移操作是差不了多少的。运行测试：