跳台阶扩展问题

题目链接

• 牛客网

题目描述

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

数据范围：1≤n≤20 进阶：空间复杂度O(1) ， 时间复杂度O(1)

刷题思路

• 我tm跳1 还剩下n-1阶 记作 G(n-1) 可选

• 我tm跳2 还剩下n-2阶 记作 G(n-2) 可选

• ....

• 我tm跳n-1 还剩下1阶 记作 G(1) 可选

• 归纳出：

  • G(n-1)=G(1)+G(2)+.....+G(n-2);
  • G(n)=G(1)+G(2)+.....+G(n-2)+G(n-1)

• 两个相减 G(n)=2G(n-1) 去递归有： G(1)=1 , G(2)=2 G(3)=2G(2)=4

总结：按照推论，结果为2的n-1幂

代码实现

/**
 * 利用Math函数计算幂
 * @param number
 * @returns {number}
 */
function jumpFloorIIOne(number) {
  return 2 ** (number - 1)
}

/**
 * 利用左移运算
 * @param number
 * @returns {number}
 */
function jumpFloorIITwo(number) {
  //     return 1<<(number-1)
  return 1 << --number
}

console.log(jumpFloorIIOne(2))
console.log(jumpFloorIITwo(4))

一些建议

数学分析推论很重要，本身就是一种方法；对于幂的运算，熟练使用Math对象的api方法，也非常建议使用左移运算，例如：

• 二进制：1--->左移一位--->10--->左移一位--->100...
• 十进制：1--->左移一位--->4--->左移一位--->8...