斐波那契数列

## 题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N &gt; 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

**示例 1：**

```txt
输入：n = 2
输出：1
```

**示例 2：**

```txt
输入：n = 5
输出：5
```

**提示：**

* 0 <= n <= 100

1. 遇到**求总数的问题**时一般考虑用**动态规划**来求。
2. 这类问题的基本思路就是**先寻找状态之间的关系**，**确定状态转移方程**，**然后使用暴力递归的方法求解**，**接着使用带有备忘录的递归**、**dp 数组的迭代解法进行优化**。
3. 类似的题目还有：
   1. [62. 不同路径](https://leetcode-cn.com/problems/unique-paths)。
   2. [64. 最小路径和](https://leetcode-cn.com/problems/minimum-path-sum)。
   3. [70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs)。

> 在解决**爬楼梯**的问题时注意的是：
> 
> 1. **要爬到第**$i$**层有两种方法**，**一种是从第**$i - 2$**层直接爬两层来到达第**$i$**层**，**另一种方法是从第**$i - 1$**层直接爬一层来到达第**$i$**层**。
> 2. **因此假设爬到第**$i$**层楼梯共有**$dp[i]$**种方法**，**则**$dp[i] = dp[i - 2] + dp[i - 1]$。

> 爬楼梯问题扩展：
>
> 1. **不能爬到 7 层及 7 层的倍数**。
>
>    这种问题的解决方法其实也很简单，就是遇到 7 层及 7 层的倍数，就把对应的值置为 0 即可。
>
>    ~~~java
>    public int climbStairs(int n) {
>        if (n == 1 || n == 2) {return n;}
>        int[] dp = new int[n+1];
>        dp[1] = 1;
>        dp[2] = 2;
>    
>        for (int i = 3; i <= n; i++) {
>            if (i % 7 == 0) {dp[i] = 0;}
>            dp[i] = dp[i-1] + dp[i-2];
>        }
>        
>        return dp[n];
>    }
>    ~~~
>
> 2. **输出每一条路径**。
>
>    这种问题可以采用 [回溯](https://notebook.ricear.com/project-21/doc-737) 的方法来进行求解。
>
>    ~~~java
>    public static List<List<Integer>> climbStairs(int n) {
>        List<List<Integer>> res = new ArrayList<>();
>        List<Integer> path = new ArrayList<>();
>    
>        if (n == 1) {return Arrays.asList(Arrays.asList(1));}
>        if (n == 2) {return Arrays.asList(Arrays.asList(1), Arrays.asList(1,2));}
>    
>        path.add(n);
>        dfs(n, path, res);
>    
>        return res;
>    }
>    
>    public static void dfs(int n, List<Integer> path, List<List<Integer>> res) {
>        if (n == 0) {
>            res.add(new ArrayList<>(path)); //  此处需要新建一个 ArrayList 对象，不然的话会导致数据发生错乱
>            return;
>        } else if (n < 0) {
>          return;
>        }
>    
>        path.add(n-1);
>        dfs(n-1, path, res);
>        path.remove(path.size()-1);
>        path.add(n-2);
>        dfs(n-2, path, res);
>        path.remove(path.size()-1);
>    }
>    ~~~

## 解题思路

### 暴力递归

* 代码

```c++
int fib(int N) {
  if (N == 1) || (N == 2) return 1;
  return fib(N - 1) + fib(N - 2);
}
```

* 递归树

![](https://notebook.ricear.com/media/202103/2021-03-01_094618.png)

### 带备忘录的递归解法

* 代码

```c++
int fib(int N) {
  if (N < 1) return 0;
  //  备忘录全初始化为 0
  vector<int> memo(N + 1, 0);
  //  初始化最简情况
  return helper(memo, N);
}

int helper(vector<int>& memo, int n) {
  //  base case
  if (n == 1) || (n == 2) return 1;
  //  已经计算过
  if (memo[n] != 0) return memo[n];
  memo[n] = memo[n - 1] + memo[n - 2];
  return memo[n]
}
```

* 递归树

![](https://notebook.ricear.com/media/202103/2021-03-01_095518.png)

![](https://notebook.ricear.com/media/202103/2021-03-01_102418.png)

此时本算法不存在冗余计算，子问题就是 `f(1)、f(2)`...`f(20)`，所以子问题个数为 o(n)，解决一个子问题的时间为 o(1)，因此本算法的时间复杂度为 o(n)。

### dp 数组的迭代解法

```c++
int fib(int N) {
  vector<int> dp(N + 1, 0);
  //  base case
  dp[1] = dp[2] == 1;
  for (int i = 1; i <= N; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
  return dp[N];
}
```

![](https://notebook.ricear.com/media/202103/2021-03-01_103126.png)

### 细节优化

斐波那契数列的状态转移方程如下：

![](https://notebook.ricear.com/media/202103/2021-03-01_104211.png)

根据斐波那契数列的状态转移方程可知，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行。所以，可以进一步优化，把空间复杂度降为 o(1)。

```c++
int fib(int n) {
  if (n == 1 || n == 2) return 1;
  int prev = 1, curr = 1;
  for (int i = 3; i <= N; i++) {
    int sum = prev + next;
    prev = curr;
    curr = sum;
  }
  return curr;
}
```

### 矩阵快速幂

1. 已知 $f(n) = f(n-1) + f(n - 2)$，令
   $$
   A_n = \begin{pmatrix}f_{n+1}\\f_{n}\end{pmatrix} = \begin{pmatrix}f_n+\;f_{n-1}\\f_n\;\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f_n\\f_{n-1}\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}A_{n-1}
   $$
   令 $B = \begin{pmatrix}1&1\\1&0\end{pmatrix}$，则
   $$
   A_n = B A_{n-1} = B^2 A_{n-2} = \cdots = B^n A_0
   $$

2. 因此可以采用 [矩阵快速幂](https://notebook.ricear.com/project-21/doc-906) 的方法计算出 $B^n$，然后用 $B^n$ 与 $A_0$ 相乘得到 $A_n$，进而可以得到 $f(n)$。

> 因为 $A(n - 1)$ 中已经存在 $f(n)$，因此我们只需要计算到 $B(n - 1)$ 即可。

> 使用矩阵快速幂算法可以将时间复杂度降至 $O(logn)$。

3. 具体代码如下：

~~~java
   public int fib(int n) {
       if (n == 1 || n == 2) {return 1;}
       int[] f = new int[n];
       f[0] = 0;
       f[1] = 1;
       f[2] = 1;
       int[][] b0 = new int[][]{{1,1},{1,0}};
       int[][] bn_1 = quickMatrixPow(b0, n-1);
       int[][] a0 = new int[][]{{f[1]},{f[0]}};
       int[][] an = matrixMultiply(bn_1, a0);
       return an[0][0];
   }
   
   /**
    * 矩阵快速幂
    * @param x 矩阵
    * @param n 幂数
    * @return  x 的 n 次幂
    */
   public int[][] quickMatrixPow(int[][] x, int n) {
       int[][] res = new int[x.length][x.length];
       for (int i = 0; i < x.length; i++) {
           res[i][i] = 1;
       }
       if (n == 0) {return res;}
       if (n == 1) {return x;}
       while (n > 0) {
           if ((n & 1) == 1) {res = matrixMultiply(res, x);}
           n >>= 1;
           x = matrixMultiply(x, x);
       }
       return res;
   }
   
   /**
    * 矩阵乘法
    * @param a 第一个矩阵
    * @param b 第二个矩阵
    * @return  两个矩阵相乘的结果
    */
   public int[][] matrixMultiply(int[][] a, int[][] b) {
       int[][] res = new int[a.length][b[0].length];
       for (int i = 0; i < a.length; i++) {    //  矩阵 a 的第 i 行
           for (int j = 0; j < b[0].length; j++) { //  矩阵 b 的第 j 列
               int sum = 0;    //  矩阵第 i 行和矩阵 b 的第 j 列相乘的结果
               for (int k = 0; k < a[i].length; k++) {
                   sum += a[i][k] * b[k][j];
               }
               res[i][j] = sum;
           }
       }
       return res;
   }
   ~~~

## 参考文献

1. [动态规划解题核心框架](https://labuladong.gitbook.io/algo/mu-lu-ye-2/mu-lu-ye/dong-tai-gui-hua-xiang-jie-jin-jie)。
1. [CodeTop035 爬楼梯](https://blog.csdn.net/Oblak_ZY/article/details/123340140)。