跳台阶扩展问题

https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey

一、问题分析

简单的万能问题分析方法，列前n项找规律

n=1，1种跳法

1

n=2，2种跳法

11，2

n=3，4种跳法

111，12，21，3

n=4，8种跳法

1111，112，121，211，22，13，31，4

n=5，16种跳法

11111，1112，1121，1211，2111，122，212，221，113，131，311，14，41，5，23，32

二、解题

可以看到规律是:target(n)=target(n-1)*2

解法1 递归

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

解法2 遍历

由于在递归过程中，会有很多重复计算，可以优化掉

    public int jumpFloorII(int target) {
        if(target <= 1) {
            return target;
        }
        int result = 1;
        for(int i = 2; i <= target; i++) {
            result = result * 2;
        }
        return result;
    }