https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode/
斐波那契数 - 图1
如图 这是斐波那契数列的转移矩阵
所以
斐波那契数 - 图2
而转移矩阵的n-2次幂可以通过快速幂计算

  1. class Solution {
  2.  public int fib(int N) {
  3.     if (N == 0) return 0;
  4.     if (N <= 2) return 1;
  5.     int[][] dp = {{1, 1},{0,0}}; // dp[0][1], dp[0][2]
  6.     int[][] ma = {{1,1},{1,0}};
  7.     N -= 2; //n-2
  8.     ma=quickMul(ma,N);
  9.     dp=mul(dp,ma);
  10.     return dp[0][0]; // dp[n]
  11. }
  12.  int[][] quickMul(int[][] ma, long N) {
  13.         int[][] ans = {{1,0},{0,1}};
  14.         // 贡献的初始值为单位矩阵
  15.         int[][] x_contribute = ma;
  16.         // 在对 N 进行二进制拆分的同时计算答案
  17.         while (N > 0) {
  18.             if (N % 2 == 1) {
  19.                 // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
  20.                 ans = mul(ans,ma);
  21.             }
  22.             // 将贡献不断地平方
  23.             x_contribute = mul(x_contribute,x_contribute);
  24.             // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
  25.             N /= 2;
  26.         }
  27.         return ans;
  28.  }
  29. int[][] mul(int[][] A, int[][] B) {
  30.         int x = A[0][0] * B[0][0] + A[0][1] * B[1][0];
  31.         int y = A[0][0] * B[0][1] + A[0][1] * B[1][1];
  32.         int z = A[1][0] * B[0][0] + A[1][1] * B[1][0];
  33.         int w = A[1][0] * B[0][1] + A[1][1] * B[1][1];
  34.         A[0][0] = x;
  35.         A[0][1] = y;
  36.         A[1][0] = z;
  37.         A[1][1] = w;
  38.         return A;
  39. }
  40. }

总结

对于任意的齐次线性方程组 斐波那契数 - 图3.
可以化为矩阵 斐波那契数 - 图4
也就可以用矩阵快速幂进行优化