/**

 * 题目：斐波那契数列   

 * 描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

 * 解决方案：方法一：递归

 *        方法二：动态规划，如果需要缓存所有的结果，用额外的数组空间进行存储。只要结果的话，就只需要中间的一个变量

 *

 * 裴波那契背景：又称黄金分割数列或者兔子数列，从第三项开始，每一项都等于前两项之和

 *  主要是递归和非递归，

 * */

public class One {    //递归    public static int One(int n) {        if(n ==0 ) {            return 0;        }        if(n == 1  ) {            return 1;        }        return One(n-1)+One(n-2);    }    //对结果要求缓存    public static int Two(int n) {        if(n<=2) return n;        int arr[] = new int[n+1];        arr[0] =0;        arr[1] =1;        for(int i=2;i<=n;i++) {            arr[i] = arr[i-1]  +arr[i-2];        }        return arr[n];    }    //最优解：    public static int Three(int n) {        if(n<2) return n;        int one = 0;        int two = 0;        int result =0;        for(int i = 2; i<=n;i++) {            result = one + two;            one = two;            two = result;        }        return result;    }}