斐波那契数列

题目描述

求斐波那契数列的第 n 项，n <= 39。

思路

• 递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。

  public int Fibonacci(int n) {
      if(n<=1)
          return n;
      int[] fib = new fib[n+1];
      fib[0] = 0;
      fib[1] = 1;
      for(int i=2; i<=n; i++){
          fib[i] = fib[i-1] + fib[i-2];
      }
      return fib[n];
  }

• 考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

  public int Fibonacci(int n) {
      if(n<=1)
          return n;
      int fib1 = 0;
      int fib2 = 1;
      int result = 0;
      for(int i=2; i<=n; i++){
          result = fib1 + fib2;
          fib1 = fib2;
          fib2 = result;
      }
      return result;
  }