青蛙跳台阶One

问题描述

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

青蛙跳台阶问题是一个经典的递归问题，也可以使用动态规划来解决。

问题分析

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

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

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

f(2) = 2

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

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

f(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;
}

动态规划的解法 Copilot 给的写法感觉更好理解

/**
 * 动态规划的解法，Copilot推荐的解法，感觉更好理解
 * @param n
 * @return
 */
static int jumpFloor(int n) {
    if(n <= 0) {
        return 0;
    }
    if(n == 1) {
        return 1;
    }
    if(n == 2) {
        return 2;
    }
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

青蛙跳台阶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) = 2f(n-1)。
注意当n为0和n为1的时候，是不满足f(n) = 2f(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. 动态规划：青蛙跳台阶、变态跳台阶