题解 | #斐波那契数列#

//递归：时间复杂度O(2^n)，空间复杂度O(栈的空间)
public class Solution {
    public int Fibonacci(int n) {
        if(n==1||n==2)
            return 1;
        else
            return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

//将已经存在的项保存在map中，不再重复计算
//时间复杂度O(n),空间复杂度O(n)
import java.util.*;
public class Solution {
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    public int Fibonacci(int n) {
        if(n==1||n==2)
            return 1;
        if(map.containsKey(n))
            return map.get(n);
        else{
            map.put(n,Fibonacci(n-1)+Fibonacci(n-2));
            return map.get(n);
        }
    }
}

//时间复杂度O(n),空间复杂度O(1)
public class Solution {
    public int Fibonacci(int n) {
        if(n==1||n==2)
            return 1;
        int a = 1,b=1,c =0;
        for(int i=3;i<=n;i++){
            c = a+b;
            a =b;
            b =c;
        }
        return c;
    }
}