剑指 offer 笔记 07 | 斐波那契数列

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

费波那契数列（意大利语：Successione di Fibonacci），又译费波拿契数、斐波那契数列、斐波那契数列、黄金分割数列。
在数学上，费波那契数列是以递归的方法来定义：

F0 = 0 (n=0)
F1 = 1 (n=1)
Fn = F[n-1]+ Fn-2

解决思路

1）递归，按照定义直接写

简单，开销大，时间比较长

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){ //递归终止条件
            return 0;
        }else if(n == 1 ||n==2){
            return 1; // 给出递归终止的处理办法
        }
        // 相同重复逻辑，分解问题的规模，自己调用自己
        return Fibonacci(n-2)+Fibonacci(n-1);
    }
}

2）用循环，不用递归，最佳解

public class Solution {
    public int Fibonacci(int n) {
        int a = 1,b = 1,c = 0;
        if(n < 0){
            return 0;
        }else if( n == 1||n == 2 ){
            return 1;
        }else{
            for (int i = 3; i <= n;i++){
                c = a+b;
                b = a;
                a = c;
            }
            return c;
        }
    }
}

题外话：算法我个人的理解，是一种思想，也是一种规律，分析出了规律，虽然我也是站在巨人的肩膀上。