题目描述

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

测试用例

用例1：

• 输入： n = 3
• 输出： 4种跳法

思路

数学归纳 —— 动态规划

假设跳 n 级台阶的跳法数量是 f(n)个。假设跳 n 级台阶的跳法数量是 f(n)个

那么根据题意，青蛙可能从 n-1 级直接跳上来，也可能从 n-2 级直接跳上来，依次类推：f(n) = f(n - 1) + f(n - 2) + ... + f(1)

同理：f(n - 1) = f(n - 2) + f(n - 3) + ... + f(1)

f(n) = 2 * f(n - 1) = 4 * f(n - 2) = ... = 2 ^ (n - 1)f(1)

其中：f(1) = 1

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入台阶的阶数: ");
const n = Number(readline());

var jumpFloorII = (n) => {
  let dp = [1, 2];

  for (let i = 2; i < n; i++) {
    dp[i] = dp.reduce((pre, cur) => pre + cur, 0) + 1; 
  }

  return dp[n - 1];
};

const res = jumpFloorII(n);
console.log(`青蛙跳上${n}级的台阶一共有${res}种跳法`);