题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

样例

输入整数 n=5 

返回 5

算法1

递推

时间复杂度O(n)

Java 代码

class Solution {
    public int Fibonacci(int n) {
        int t1 = 0, t2 = 1, t3; 
        while(n-- > 0){
            t3 = t1 + t2;
            t1 = t2;
            t2 = t3;
        }
        return t1;
    }
}

递归

时间复杂度O(n)

Java 代码

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