[算法练习] 青蛙跳

题目

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

分析

台阶 解法
1 1
2 1,1 2
3 1,1 2,1 1,1,1
4 1,1,1 2,1,1 1 1,1,1,1 1,1,2 2,2
....

由上面可以看出第 N 次的解法数量是 N-1数量加上 N-2 数量
F(n) = F(n-1) + F(n-2)
和斐波那契数列类似, 可以用递归实现

代码实现

    /**
     * 暴力计算, 递归, 自上向下
     */
    @Test
    public void test() {
        int ret = JumpFloor(10);
        System.out.println("test: " + ret);
    }

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

  
    public int[] mCache = null;
    /**
     * 通过缓存优化计算耗时, 空间换时间, 自上向下
     */
    @Test
    public void test2() {
        int target = 10;
        mCache = new int[target + 1];
        int ret = JumpFloor2(target);
        System.out.println("test2: " + ret);
    }

    public int JumpFloor2(int target) {
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        // 缓存计算结果, 如果未设值就赋值, 如果有就直接返回, 不需要再重复计算
        if (mCache[target] == 0) {
            mCache[target] = JumpFloor(target - 1) + JumpFloor(target - 2);
        }
        return mCache[target];
    }

    /**
     * 动态规划, 自下向上
     */
    @Test
    public void test3() {
        int target = 10;
        int ret = JumpFloor3(target);
        System.out.println("tes3: " + ret);
    }

    public int JumpFloor3(int target) {
        int[] cache = new int[target + 1];
        cache[0] = 1;
        cache[1] = 1;
        for (int index = 2; index <= target; index++) {
            cache[index] = cache[index - 1] + cache[index - 2];
        }
        return cache[target];
    }