# LeetCode Easy 509. Fibonacci Number

tags: leetcode

問題

• Explore
• Problems

フィボナッチ数列とはある数が前の2つの数を足した数であるような数列で, $0$, $1$から始まるようなものである.つまり

F(0) = 0, F(1) = 1 F(N) = F(N-1) + F(N - 2), for N > 1

$N$が与えられた時, F(N)を求めろ

解法1(recursive)

• 定義に従って書きます
• 基底はN==0のときとN==1のときで, それぞれ返す値は0, 1です
  • つまりN<=1ならばNを返します
• それ以外の場合では再帰的にfib(N-1) + fib(N-2)を返します
• 以下のように再帰的に関数が呼び出されます

• 空間計算量は上のように$O(N)$種類のfibが呼び出されるので$O(N)$
• 時間計算量は上のように指数関数的に関数が呼び出されるため$O(2^{N})$
• つまり非常に計算効率が悪いです

Python

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
          return N
        else:
          return self.fib(N-1) + self.fib(N-2)

C++

class Solution {
public:
    int fib(int N) {
        if (N <= 1) {
          return N;
        } else {
          return fib(N-1) + fib(N-2);
        }
    }
};

解法2(iterative)

• 時間計算量を改善するためにメモ化という手法を使います
• 上の再帰では同じ関数を何度も使っています
  • 同じ関数では計算結果が同じになります
• この計算結果を配列などで用いて保存することで不必要な計算の繰り返しを防ぎます
• ここでは長さN+1のf_listという配列を使います
  • f_list[i]がfib(i)の計算結果を保持するようにします
• そうすると繰り返し文を使って上の計算をすることが可能です
• 以下のように配列は計算の結果を保存して再利用します

• ただし, N==0の時に配列の外を参照しないように場合分けをします
• 空間計算量は$O(N)$
• 時間計算量は配列を作るのに$O(N)$, 配列を参照するのに$O(1)$

Python

class Solution:
    def fib(self, N: int) -> int:
      if N == 0:
        return 0
      f_list = [0] * (N+1)
      f_list[1] = 1
      for i in range(2, N+1):
        f_list[i] = f_list[i-1] + f_list[i-2]
      return f_list[N]

C++

class Solution {
public:
    int fib(int N) {
      if (N == 0) {
        return 0;
      }
      vector<int> f_arr(N+1);
      f_arr[1] = 1;
      for (int  i = 2; i <= N; i++) {
        f_arr[i] = f_arr[i-1] + f_arr[i-2];
      }
      return f_arr[N];
    }
};

解法3(iterative)

• 上の結果ではまだ不十分です
• fib(i)の計算に使うのはfib(i-1)とfib(i-2)の計算結果だけなのでそれだけを保存します
• 空間計算量はこの工夫によって$O(1)$
• 時間計算量は$O(N)$となります

Python

class Solution:
    def fib(self, N: int) -> int:
      if N <= 1:
        return N
      prev1 = 0
      res = 1
      for _ in range(2, N+1):
        prev2 = prev1
        prev1 = res
        res = prev1 + prev2
      return res

C++

class Solution {
public:
    int fib(int N) {
      if (N <= 1) {
        return N;
      }
      int prev1 = 0;
      int res = 1;
      for (int i = 2; i <= N; i++) {
        int prev2 = prev1;
        prev1 = res;
        res = prev1 + prev2;
      }
      return res;
    }
};