剑指offer_10_斐波那契数列

• 2019 年 10 月 6 日
• 筆記

题目：求斐波那契数的第n项

描述：写一个函数，输入n，求斐波那契数的第n项，斐波那契数的定义如下

       { 0                    n = 0  f(n) = { 1                    n = 1         { f(n - 1) + f(n - 2)  n > 1

说白了就是从第二项开始，每项都是前两项的和：

    0 1 1 2 3 5 8 13 21.....

第一种方法递归：

public static int fibonacci(int number) {      if(number < 0) {           return 0;       }      if (number <= 1) {           return number;       }      return fibonacci(number-1) + fibonacci(number -2);  }

第二种方法动态规划1：

public static int fibonacci2(int number) {      if (number < 0) {          return 0;      }      if (number <= 1) {          return number;      }        int[] arr = new int [number + 1];      arr[0] = 0;      arr[1] = 1;      for (int i = 2; i <= number; i++) {          arr[i] = arr[i-1] + arr[i-2];      }      return arr[number];  }

第二种方法动态规划2：

publicstatic int fibonacci(int number) {        if (number < 0) {          return 0;        }        if (number <= 1) {          return number;        }        int[] arr = new int [3];        arr[0] = 0;        arr[1] = 1;        for (int i = 2; i <= number; i++) {            // 这里是为了节约空间 循环利用数组            arr[i % 3] = arr[(i-1) % 3] + arr[(i-2) % 3];        }        return arr[number % 3];  }

总结：递归方法在求当n很大的时候会占用很大的栈空间，效率比较低，不足以拿到offer，建议用动态规划。

相关的题目还有：青蛙跳台阶问题、矩形覆盖问题等。