跳台阶

题目链接

• 牛客网

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤n≤40 要求：时间复杂度：O(n) ，空间复杂度：O(1)

刷题思路

总共有n个台阶，假如

• 第一次跳1阶，即：a1=1,则还剩下n-1可以再第二次选择，那么共n-1个台阶，会有多少种跳法？？？
• 第一次跳2阶，即：a1=2,则还剩下n-2可以再第二次选择，那么共n-2个台阶，会有多少种跳法？？？

问题很容易就演变成G(n)=G(n-1)+ G(n-2)

这不就是斐波那契数列么？？？？ 可以参考：【入门】斐波那契数列

代码实现

/**
 * 【简单】跳台阶  递归，要么跳一阶，要么跳两阶
 * 思路： 对于第number台阶，只能从第number-1或者number-2上跳上来
 * 记作： G(number)=G(number-1)+G(number-2)
 * 即： 从第number-1跳上来的次数+从第number-2上跳上来的次数
 *
 */

/**
 * 递归实现
 */
function jumpFloorOne(number) {
  // 递归，要么跳一阶，要么跳两阶
  return number < 3 ? number : jumpFloorOne(number - 1) + jumpFloorOne(number - 2)
}

/**
 * 非递归调用
 */
function jumpFloorTwo(number) {
  let a = 1
  let b = 2
  let result = 1

  for (let index = 3; index <= number; index++) {
    result = a + b
    a = b
    b = result
  }
  return result
}

console.log(jumpFloorOne(7))
console.log(jumpFloorTwo(7))

一些建议

• 数学分析、逻辑思维很重要
• 熟练斐波那契数列