难易程度：Hard
是否重点：10 分
掌握程度：轻松写出二叉树遍历、八皇后、背包问题、DFS 的递归代码

  1. 斐波那契数列、求阶乘
  2. 归并排序、快速排序、二叉树的遍历、求高度
  3. 回溯八皇后、背包问题

练习：

剑指 Offer 10- I. 斐波那契数列

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

求余运算 (a + b) % p = (a % p + b % p) % p

(5 + 14) % 3 = 1 = (
5 % 3 + 14 % 3) % 3
⚠️ n > 44后结果移除
n=0 => 1
n=1 => 1
n=2 => 2
特殊处理

  1. if (n == 0 || n==1) return 1;

方法1: 递归（超时）

  1. var fib = function(n) {
  2.     if (n < 2) return n;
  3.     return (fib(n-1) % 1000000007 + fib(n-2) % 1000000007) % 1000000007
  4. };

方法2: 动态规划

  1. var fib = function(n) {
  2.     if (n < 2) return n;
  3.     const P = 1000000007
  4.     let dp = new Array(n+1).fill(null)
  5.     dp[0] = 0
  6.     dp[1] = 1
  7.     for (let i = 2; i <= n; i++) {
  8.         dp[i] = (dp[i-1] % P + dp[i-2] % P) % P;
  9.     }
  10.     // console.log(dp)
  11.     return dp.pop();
  12. };

改造： 迭代

  1. var fib = function(n) {
  2.     if (n < 2) return n;
  3.     let P = 1000000007;
  4.     let a = 0, b =1;
  5.     for (let i = 2; i <= n; i++) {
  6.         [a, b] = [b%P, (a+b)%P]
  7.     }
  8.     return b
  9. };

方法3: 尾递归

  1. var fib = function(n) {
  2.     if (n < 2) return n;
  3.     return tail(n, 1, 1)
  4. };
  6. function tail (n, res1, res2) {
  7.     // console.log(n, res1, res2)
  8.     const P = 1000000007;
  9.     if (n == 1) return res1; 
  10.     // if (n == 2) return res2;// 同上
  11.     return tail(n-1, res2 % P, (res1+res2)%P);
  12. }
  14. fib(8) // 21

第n位[0， 1， 1]， 从1开始
若n位[1, 1, 2], 从0开始

  1. function fiboTail(n, res1 = 1, res2 = 1) {
  2.     // console.log(n, res1, res2)
  3.     if (n == 0) return res1;
  4.     return fiboTail(n-1, res2, res1 + res2)
  5. }
  7. console.log(fiboTail(8)) // 34

剑指 Offer 10- II. 青蛙跳台阶问题 (同上)