【算法题】小兔子爬楼梯

介绍

小兔子想去月球上旅行，假设小兔子拥有一个 n 阶梯子，当你爬完 n 层就可以到达月球，小兔子每次可以跳 1 或者 2 个台阶，小兔子有多少种跳法可以到达月球呢？

给定 n 是一个正整数，代表梯子的阶数，当 n=2 时，小兔子有 2 种跳法到达月球；当 n=3 时，小兔子有 3 种跳法跳到月球，以此类推，解释如下图所示：

img

实现思路提示

这里为同学提供以下两种解题思路。

1. 递归

可以使用递归来实现，具体思路如下：

  • 当阶梯数为 0 时，只有 0 种方法；当阶梯数为 1 时，只有 1 种方法；当阶梯数为 2 时，只有 2 种方法，所以当阶梯数 n 小于等于 2 时，可以直接返回值。
  • 如果阶梯数大于 2，就递归。

2. 动态规划

可以使用动态规划来实现，具体思路如下：

  • 当阶梯数 n 为 0 时，直接返回 0。
  • 当阶梯数 n 为 1 时，直接返回 1。
  • 当阶梯数大于 1 时，假设有 i 阶梯子需要爬，就有 dp[i] 中方法。
  • 3 阶以上的梯子，都满足一个规律：dp[i] = dp[i-1] + dp[i-2]。

解题思路不只这两种，同学们可以自由发挥。

准备

本题已经内置了初始代码，打开实验环境，目录结构如下：

1
2
3
├── js
│   └── index.js
└── index.html

其中：

  • js/index.js 是实现函数的 js 代码文件。
  • index.html 是显示结果的页面。

选中 index.html 右键启动 Web Server 服务（Open with Live Server），让项目运行起来。打开环境右侧的【Web 服务】，当前页面显示如下。

图片描述

目标

请完善 index.js 文件中的代码，页面显示结果如下：

图片描述

规定

  • 请严格按照考试步骤操作，切勿修改考试默认提供项目中的文件名称、文件夹路径等。
  • 满足题目需求后，保持 Web 服务处于可以正常访问状态，点击「提交检测」系统会自动判分。

总通过次数: 2214 | 总提交次数: 2246 | 通过率: 98.6%

难度: 简单 标签: 2022, 省模拟赛, Web 前端, JS 函数封装, 树

题解

1
2
3
4
5
6
7
8
9
10
11
12
const climbStairs = (n) => {
 if (n === 0) {
    return 0
 }
 if (n === 1) {
    return 1
 }
 if (n === 2) {
    return 2
 }
 return climbStairs(n - 1) + climbStairs(n - 2);
}