题解 | 斐波那契数列

方法一：循环枚举（也可理解为滚动数组（变量）优化DP），时间复杂度O(k)，空间复杂度O(1)

#include <iostream>

constexpr int P = 1E9 + 7;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int k;
  std::cin >> k;

  if(k < 3){
    std::cout << "1\n";
    return 0;
  }

  int cur = 1, prev = 1;
  for(int i = 3; i <= k; i++){
    int tmp = (cur + prev) % P;
    prev = cur;
    cur = tmp;
  }

  std::cout << cur << "\n";

  return 0;
}

方法二：记忆化dfs，时间复杂度O(k)，空间复杂度O(k)

#include <iostream>
#include <vector>
#include <functional>

constexpr int P = 1E9 + 7;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int k;
  std::cin >> k;
  
  std::vector<int> f(k + 1);
  std::function<int(int)> dfs = [&](int n){
    if(n == 1 || n == 2){
      return 1;
    }
    if(f[n]){
      return f[n];
    }

    return f[n] = (dfs(n - 1) + dfs(n - 2)) % P;
  };

  std::cout << dfs(k) << "\n";

  return 0;
}

方法三：矩阵快速幂，时间复杂度O(logk)，空间复杂度O(1)

#include <iostream>
#include <vector>

using Matrix = std::vector<std::vector<int>>;

constexpr int P = 1E9 + 7;

Matrix mul(const Matrix& A, const Matrix& B){
  Matrix res(A.size(), std::vector<int>(B[0].size()));
  for(int i = 0; i < A.size(); i++){
    for(int j = 0; j < A[0].size(); j++){
      for(int k = 0; k < B[0].size(); k++){
        res[i][k] = (res[i][k] + (1LL * A[i][j] * B[j][k] % P)) % P;
      }
    }
  }
  return res;
}

Matrix power(Matrix A, int b){
  Matrix res(A.size(), std::vector<int>(A[0].size()));
  for(int i = 0; i < res.size(); i++){
    res[i][i] = 1;
  }
  for(; b; A = mul(A, A), b >>= 1){
    if(b & 1){
      res = mul(res, A);
    }
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int k;
  std::cin >> k;

  if(k < 3){
    std::cout << "1\n";
    return 0;
  }

  Matrix A(1, std::vector<int>(2));
  A = {{1, 1}};

  Matrix B(2, std::vector<int>(2));
  B = {
    {0, 1},
    {1, 1}
  };

  auto Bk_1 = power(B, k - 1);
  auto ans = mul(A, Bk_1);

  std::cout << ans[0][0] << "\n";

  return 0;
}