青蛙跳台阶问题

青蛙跳台阶One

问题描述

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

问题分析

设f(n)表示青蛙跳上n级台阶的跳法数。
当只有一个台阶时，即n = 1时， 只有1中跳法：一次跳上去。

当n = 2时，有两种跳法：

1. 可以一次跳一阶，2次跳上去。
2. 也可以一次跳两阶。

当n = 3 时，有3种跳法：

1. 一次跳一阶，一次跳两阶，跳2次。
2. 一次跳两阶，一次跳一阶，跳2次。
3. 一次跳一阶，跳3次。

当n很大时，青蛙在最后一步跳到第n级台阶时，有两种情况：

1. 一种是青蛙在第n-1个台阶，跳1个台阶到第n个台阶，那么青蛙跳完前面n-1个台阶，就有f(n-1)种跳法，这是一个子问题。
2. 另一种是青蛙在第n-2个台阶，跳2个台阶到第n个台阶，那么青蛙完成前面n-2个台阶，就有f(n-2)种情况，这又是另外一个子问题。

两个子问题构成了最终问题的解，所以当n>=3时，青蛙就有f(n)=f(n-1)+f(n-2)种跳法。

上面的分析过程，用数学方程表达如下：

算法实现

递归解法

    /**
     * 递归解法
     *
     * @param n 台阶数 n>=3
     * @return
     */
    static int frogJumpRecursively(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            return frogJumpRecursively(n - 1) + frogJumpRecursively(n - 2);
        }
    }

动态规划解法

    /**
     * 动态规划解法
     *
     * @param n 台阶数 n>=3
     * @return
     */
    static int frogJump(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        //n从3开始，preTwo就代表n为1时的跳法数
        int preTwo = 1;
        //n从3开始，preOne就代表n为2时的跳法数
        int prepOne = 2;
        //跳上n阶所需要的总的跳法
        int jumpN = 0;
        for (int i = 3; i <= n; i++) {
            jumpN = preTwo + prepOne;
            preTwo = prepOne;
            prepOne = jumpN;
        }
        return jumpN;
    }

青蛙跳台阶Two

问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级，也可以跳上，……也可以跳上n级，那么青蛙跳上一个n级的台阶总共有多少种跳法？

问题分析

关于本题，存在n级台阶1次就跳上去的跳法。分析如下:
要跳上第n级台阶，可以从第n−1级台阶一次跳上来，也可以可以从第n−2级台阶一次跳上来，也可以可以从第n−3级台阶一次跳上来，…，也可以可以从第1级台阶一次跳上来，也可以从第0级台阶一次跳上来。那么问题就很简单啦，同样的，令f(n) 表示跳上第n级台阶有几种跳法。则有如下递推公式:

f(n)=f(n−1)+f(n−2)+...+f(1)+f(0)
f(n-1)=f(n−2)+...+f(1)+f(0)
两式相减得：f(n)-f(n-1)=f(n-1)，所以f(n) = 2*f(n-1)。

注意当n为0和n为1的时候，是不满足f(n) = 2*f(n-1)这个公式的。
f(0)=1：表示一次跳n级台阶的跳法
f(1)=1: 表示一次跳一级台阶（也可以认为是和f(0)是等价的，表示一次跳n级台阶的跳法，只不过此时n为1）。

综上所述：

算法实现

递归实现

    /**
     * 递归实现
     *
     * @param n
     * @return
     */
    static int frogJumpRecursively(int n) {
        if (n == 0 || n == 1) return 1;
        return 2 * frogJumpRecursively(n - 1);
    }

循环实现

/**
     * 循环实现
     *
     * @param n
     * @return
     */
    public int JumpFloorII(int n) {
        if (n == 0 || n == 1) return 1;
        int result = 1;
        while (n > 1) {
            result *= 2;
            n--;
        }
        return result;
    }

注意，当n > = 2时：
f(n)=2f(n−1)=4f(n−2)=8f(n−3)=...，即

f(n)=f(n−1)=f(n−2)=f(n−3)=...=f(n−(n−1))=f(1)

所以当n > = 2时也可以直接计算

public static int JumpPower2(int n) {
    if (n == 0 || n == 1) return 1;
    return 1 << (n - 1);
}

参考链接：

1. 青蛙跳台阶问题，常见面试算法题，斐波那契数列（Fibonacci Sequence）
2. 面试题之青蛙变态跳台阶问题
3. 动态规划：青蛙跳台阶、变态跳台阶