剑指offer10 青蛙跳台阶

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解答

动态规划

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
  if(n<=1) return 1;
  let fibNMinus2 = 1;
  let fibNMinus1 = 1;
  let fib = n
  for(let i= 2;i<= n;i++) {
      fib = (fibNMinus1 + fibNMinus2) % (1e9+7) // 在循环里面计算才不会ac不通过，取模精确度准确
      fibNMinus2 = fibNMinus1
      fibNMinus1 = fib
  }
  return fib
};

类似题目

70. 爬楼梯

TIP

本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和

爬上 n-1 阶楼梯的方法数量。因为再爬1阶就能到第n阶 爬上 n-2 阶楼梯的方法数量，因为再爬2阶就能到第n阶 所以我们得到公式 dp[n] = dp[n-1] + dp[n-2] 同时需要初始化 dp[0]=1 和 dp[1]=1 时间复杂度：O(n)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

// 时间/空间复杂度均为: O(n)

优化复杂度：

dp[i] 只与 dp[i-1] 和 dp[i-2] 有关，没有必要存储所有计算过的 dp 项。用两个临时变量去存这两个状态就好。

const climbStairs = (n) => {
  let prev = 1;
  let cur = 1;
  for (let i = 2; i < n + 1; i++) {
    const temp = cur;   // 暂存上一次的cur
    cur = prev + cur;   // 当前的cur = 上上次cur + 上一次cur
    prev = temp;        // prev 更新为 上一次的cur
  }
  return cur;
}

// 空间复杂度O(1)

面试题08.01 三步问题

TIP

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

/**
 * @param {number} n
 * @return {number}
 */
var waysToStep = function(n) {
  let dp = new Array(n)
  dp[0]=1
  dp[1]=2
  dp[2]=4
  if(n<=3) {
      return dp[n-1]
  } else {
      for(let i=4;i<=n;i++) {
          dp[i-1] = (dp[i-2]+dp[i-3]+dp[i-4]) % (Math.pow(10,9)+7) // 1e9+7
      }
      return dp[n-1]
  }
};