斐波那契数列

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

首先给出斐波那契数列的定义

F(1) = 1，F(2) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 3，n ∈ N*）

解法一：递归解法

不建议使用，如果出现大规模的测试用例，会导致栈溢出

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

解法二：非递归解法

public class Solution {
    public int Fibonacci(int n) {
    	// f(1) = 1
        int preNum = 1;
        // f(2) = 0
        int prePreNum = 0;
        // 保存每次运算的结果
        int result = 0;
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }
        for(int i = 2; i <= n; i++) {
            result = preNum + prePreNum;
            prePreNum = preNum;
            preNum = result;
        }
        return result;
    }
}