斐波那契数列的公式为

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

最直观的方式是使用递归，但是递归需要一定的栈空间，而且有重复计算，例如：f(8) = f(7) + f(6),f(7) = f(6) + f(5) 这样，会多次计算，可以使用循环的方式，每次计算之后累加，如从f(2)开始，一直计算到f(n)，期间一直保存这f(cur-1),f(cur-2)

递归程序

public int get(int i) {
	if(i<0)return -1;
	if(i == 0||i == 1)return i;
	return get(i-1) + get(i-2);
}

循环程序

public int get(int i) {
    if(i < 0) return -1;
    if(i == 0||i == 1)return i;
    int N$2 = 0, N$1 = 1,idx = 2,ret=0;
    while(idx <= i) { // 0 1 1 2 3 5 8
        ret = N$2 + N$1;
        N$2 = N$1;
        N$1 = ret;
        idx++;
    }
    return ret;
}

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法，返回3

规则
输入： int n 楼梯的长度
输出：int 多少种方法
case：

n 小于0
n等于0
n等于1
n等于2

思路

假设第n个台阶有f(n)种方法，f(n-1)种再加上一步1个台阶就到达n了，此时有f(n-1)种，f(n-2)楼梯的时候再加上一步2个台阶就到达n了，此时有f(n-2)种，因此：f(n) = f(n-1)+f(n-2)，f(0) = 0 ，f(1) = 1 f(2) = 2

代码

public int climbStairs(int i) {
        if (i <= 0) {
            return 0;
        }
        if (i == 1) {
            return i;
        }
        int N$2 = 1, N$1 = 1, idx = 2, ret = 0;
        while (idx <= i) { // 0 1 1 2 3 5 8
            ret = N$2 + N$1;
            N$2 = N$1;
            N$1 = ret;
            idx++;
        }
        return ret;
    }