首页
   /       /   
蓝桥杯(web组)题解-小兔子爬楼梯
3月
11
蓝桥杯(web组)题解-小兔子爬楼梯
作者:大彭Sir    分类: 学习笔记

背景介绍

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

给定 n 是一个正整数,代表梯子的阶数,当 n=2 时,小兔子有 2 种跳法到达月球;当 n=3 时,小兔子有 3 种跳法跳到月球,以此类推

实现思路提示

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

  1. 递归

可以使用递归来实现,具体思路如下:

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

  1. 动态规划

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

当阶梯数 n 为 0 时,直接返回 0。
当阶梯数 n 为 1 时,直接返回 1。
当阶梯数大于 1 时,假设有 i 阶梯子需要爬,就有 dp[i] 中方法。
3 阶以上的梯子,都满足一个规律:dp[i] = dp[i-1] + dp[i-2]。
解题思路不只这两种,同学们可以自由发挥。

考试要求

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

完整代码

const climbStairs = (n) => {
    if (n <= 2) {
        return n
    } else if (n > 2) {
        return climbStairs(n - 1) + climbStairs(n - 2)
    }

}
module.exports = climbStairs;
本文标签:标签: 递归算法 js
责任声明:本页信息由网友自行发布或来源于网络,真实性、合法性由发布人负责,请仔细甄别!本站只为传递信息,我们不做任何双方证明,也不承担任何法律责任。文章内容若侵犯你的权益,请联系本站删除!
转载声明:本文作者大彭Sir,如需转载请保留文章出处!原文链接请自行复制!

Theme By Brief 鄂ICP备19010459号

站长统计 sitemap

首页

分类

友链

登录