题解 | #斐波那契数列#

题目(Java题解)

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

示例

input:
    4
output:    
    3

解题思路

看到这种简单的问题切忌上来提笔就写，首先需要判断的是，是否存在越界问题，其次要考虑最优解，显然对于这个老生常谈的递归问题很多人可以得到一个解决方案，但是如何对已有的方案进行优化你也应该了然如心，无论是剪枝抑或是通过额外空间存储数据的方式。
时间复杂度：
基本解：O(N^2)
dp解：O(N)

实例代码

基本解

public class Solution {
   public int Fibonacci(int n) {
       if(n == 0 || n == 1){
           return n;
       }
       return Fibonacci(n - 1) + Fibonacci(n - 2);
   }
}

dp解

public class Solution {
   public int Fibonacci(int n) {
       int a = 0;
       int b = 1;
       for(int i = 2; i <= n; i++){
           int sum = a + b;
           a = b;
           b = sum;
       }
       return sum;
   }
}