• 题目难度：入门

  • 题目描述：

    大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
    斐波那契数列是一个满足以下条件的数列：
    图片说明
  • 数据范围：1 ≤ n ≤ 40
  • 要求：空间复杂度 O(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn) 的解法
  • 输入描述：一个正整数n
  • 返回值描述：输出一个正整数。

  • 示例一：

    输入：4
    返回值：3
    说明：根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。

  • 思路一：递归

    提交结果：答案正确 运行时间：205ms 占用内存：460KB
    时间复杂度:O(2)

    class Solution {
public:
  int Fibonacci(int n) {
      if (n > 0 && n <= 2) return 1;
      else return Fibonacci(n-1) + Fibonacci(n-2);
  }
};

  • 思路二：记忆化搜索

    时间复杂度:O(n)
    提交结果：答案正确 运行时间：4ms 占用内存：512KB

    class Solution {
public:
  int m[50] {0};
  int Fibonacci(int n) {
      if(n <= 2) m[1] = m[2] = 1;
      if(m[n] != 0) return m[n];
      else {
          m[n] = Fibonacci(n-1) + Fibonacci(n-2);
          return m[n];
      }
  }
};

  • 思路三：动态规划

    时间复杂度:O(n)
    提交结果：答案正确 运行时间：4ms 占用内存：408KB

    class Solution {
public:
  int dp[50]{0};
  int Fibonacci(int n) {
      dp[1] = dp[2] = 1;
      for (int i = 3; i <= n; ++i) dp[i] = dp[i-1] + dp[i-2];
      return dp[n];
  }
};

    滚动数组优化；
    提交结果：答案正确 运行时间：3ms 占用内存：436KB

    class Solution {
public:
  int Fibonacci(int n) {
      int a = 1, b = 1, c = 1;
      for (int i = 3; i <= n; ++i) c = a + b, a = b, b = c;
      return c;
  }
};

    😘😘😘😘😘😘😘😘😘😘😘😘😘