【每日一题】【递归实现、自下而上、优化】-2022年1月12日-NC68 跳台阶

描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：0 \leq n \leq 400≤n≤40
要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1)

方法1：函数递归

public class Solution {

    public int jumpFloor(int target) {

        if(target == 1 || target == 0) {

            return 1;

        }

        return jumpFloor(target - 1) + jumpFloor(target - 2);

    }

}

方法2：自下而上，使用数组

public class Solution {

    public int jumpFloor(int target) {

        int[] res = new int[target + 1];

        res[0] = 1;

        res[1] = 1;

        for(int i = 2; i <= target; i++) {

            res[i] = res[i - 1] + res[i - 2];

        }

        return res[target];

    }

}

注意：数组名起为res/f都行

方法3：变量空间的优化

public class Solution {

    public int jumpFloor(int target) {

        int p = 1, q = 1;

        //和自下而上的方法使用相同的循环结构

        for(int i = 2; i <= target; i++) {

            int temp = p;

            p = p + q;

            q = temp;

        }

        return p;

    }

}

注意：可以和自下而上基于数组的方法使用相同的循环结构

巴特西

【每日一题】【递归实现、自下而上、优化】-2022年1月12日-NC68 跳台阶

最新文章

热门文章