青蛙跳台阶 - wangshengliang

题目#

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。假设台阶总共有 n 级，问共有多少种不同的跳法，让青蛙从第 0 级（地面）跳到第 n 级台阶？

示例 1

若 n = 1，只有 1 级台阶，那青蛙只能跳 1 步到达，所以跳法数为 1。

示例 2

若 n = 2，可以：

连续跳 1 级 + 1 级

一次跳 2 级

两种方案，因此跳法数为 2。

示例 3

若 n = 3，跳法如下：

1 + 1 +1

1 + 2

2 + 1

共有 3 种不同的跳法。

目标：给定 n，求能到达第 n 级台阶的 所有不同跳法 数量。

解题思路#

像这种题目，就比较隐晦了，不会直接得到状态转移方程，而是需要你自己分析来得到这个方程。

分析：

n = 1，就一种跳法，因此 dp[1] = 1
n = 2，有两种跳法，因此 dp[2] = 2
n = 3，有 3 种跳法，分别是 1 + 1 + 1，1 + 2，2 + 1，因此 dp[3] = 3

好像还看不出规律，怎么办？那就继续多分析几个值

n = 4，有 5 种跳法，分别是 1 + 1 + 1 + 1，1 + 1 + 2，1 + 2 + 1，2 + 1 + 1，2 + 2，因此 dp[4] = 5
n = 5，有 8 种跳法，分别是 1 + 1 + 1 + 1 + 1，1 + 1 + 1 + 2，1 + 1 + 2 + 1，1 + 2 + 1 + 1，2 + 1 + 1 + 1，2 + 2 + 1，2 + 1 + 2，1 + 2 + 2，因此 dp[5] = 8

至此，我们好像已经看到规律了：

dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
dp[5] = 8
…

好像当前跳 n 阶的跳法等于 n - 1 阶跳法和 n - 2 阶跳法之和。

这个分析对不对呢？其实是对的

假设现在青蛙🐸在第 4 阶，那么它跳上第 5 阶就只能是跳 1 级，也就是说，跳上第 4 阶有 n 种跳法，现在从第 4 阶上跳上第 5 阶也就是 n 种跳法。

假设现在青蛙🐸在第 3 阶，那么它跳上第 5 阶就是跳 2 级。也就是说，跳上第 3 阶有 m 种跳法，现在从第 3 阶上跳上第 5 阶也就是 m 种跳法。有人说，不对‼️从第 3 阶跳上第 5 阶不是还能够 1 级 1 级的跳么？但是你想一想🤔如果是跳 1 级，那就是在第 4 阶，不就回归到了第 4 阶跳上第 5 阶有多少种跳法了么？

因此，最终我们推导出来状态转移方程为：

dp[i]=dp[i−1]+dp[i−2]

初始条件：

dp[0]=0,dp[1]=1

没错，最终推导出来的状态转移方程仍然是斐波那契数列的方程，只不过这一次更加的隐蔽，需要我们自己推导出来。

实现代码#

这一次我们就使用另外一种存储状态的方式：记忆化搜索。（自上而下）

function fibonacciMemo(n) {
  // 首先创建一个 memo 数组作为缓存
  const memo = new Array(n + 1).fill(null)

  function helper(k) {
    if (k < 2) return k

    // 接下来就从缓存里面去找结果
    // 如果不等于 null，说明这一位的斐波那契数是之前计算过的
    // 直接从缓存中去获取即可
    if (memo[k] !== null) return memo[k]

    // 在计算的同时，做了缓存
    memo[k] = helper(k - 1) + helper(k - 2)

    return memo[k]
  }

  return helper(n)
}

-EOF-