509. Fibonacci Number

题目

题意分析

本题需要计算0~30之内的斐波那契数列的值。

本题考点

斐波那契数列的不同计算方法。

解法I - 递推

我们可以直接通过递推公式F(N) = F(N - 1) + F(N - 2), F(1) = 1, F(0) = 0，来递推出最后的结果。

实现

class Solution {
  public int fib(int N) {
    if (N < 2) // f(1) = 1, f(0) = 0
      return N;
    
    int fn_2 = 0, fn_1 = 1;
    
    int fn = 0;
    
    // 顺序递推
    for (int k = 2; k <= N; k++) {
      fn = fn_1 + fn_2;
      fn_2 = fn_1;
      fn_1 = fn;
    }
    
    return fn;
  } 
} 

解法II - 递归

通过递推公式，使用递归实现。

注意，因直接根据递推公式进行递归的时间复杂度是O(2ⁿ)，故当N较大时将会导致超时以及栈溢出的情况。

我们在此需要通过记忆化搜索来实现。

实现

class Solution {
  // 定义一个Hashap，来存我们之前已经计算过的答案
  private Map<Integer, Integer> fibs = new HashMap<>();

  public int fib(int N) {
    // n = 1 与 n = 0 时，记录结果，直接返回
    if (N < 2) {
      fibs.put(N, N);
      return N;
    }

    // 如果已经计算过了，则直接返回
    Integer fn = fibs.get(N);
    if (fn != null) {
      return fn;
    }

    // 如果fn-1 与 fn-2都计算过了
    // 记录当前结果，并直接返回
    Integer fn_1 = fibs.get(N - 1), fn_2 = fibs.get(N - 2);
    if (fn_1 != null && fn_2 != null) {
      int result = fn_1 + fn_2;
      fibs.put(N, result);
      return result;
    }

    return fib(N - 1) + fib(N - 2);
  }
}