[7] 斐波那契数列(入门)
[7] 斐波那契数列(入门)

题目描述

大家都知道斐波那契数列,现在要求输入一个整数 n,请你输出斐波那契数列的第 n 项(从 0 开始,第 0 项为 0,第 1 项是 1)。
n <= 30
输入:4
返回值:3

解题思路

递归

/**
 * 递归
 * T(2n) S(递归栈空间)
 */
public int Fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

递归缓存

用哈希表把每次递归结果缓存起来,避免重复计算。
/**
 * 递归缓存
 * T(n) S(n+递归栈空间)
 */
public int Fibonacci(int n) {
    Map<Integer, Integer> map = new HashMap<>();
    return Fib(n, map);
}

public int Fib(int n, Map<Integer, Integer> map) {
    if (n <= 1) {
        return n;
    }
    if (map.containsKey(n)) {
        return map.get(n);
    }
    int a = Fib(n - 1, map) + Fib(n - 2, map);
    map.put(n, a);
    return a;
}

动态规划

/**
   * 动态规划
   * T(n) S(1)
   */
  public static int Fibonacci(int n) {
      int sum = 0;
      int lastFrist = 0;  // f(n-1)
      int lastSecond = 1; // f(n-2)
      // 0 和 1 直接返回
      for (int i = 2; i <= n; i++) {
          sum = lastFrist + lastSecond;   // f(n-1) + f(n-2)
          lastFrist = lastSecond;
          lastSecond = sum;
      }
      return n <= 1 ? n : sum;
  }