面试题10：斐波那契数列

题目一：求斐波那契数列的第n项
写一个函数，输入n，求斐波那契数列的第n项
思路：不要用递归，效率太低，会栈溢出；用循环代替
解决方案：

public class Question10 {
    public static int Fibonacci(int n){
        int[] result = new int[]{0,1};
        if (n < 2) return result[n];
        int fibNminusOne = 1;
        int fibNminusTwo = 0;
        int fibN = 0;
        for (int i=2; i<=n; i++){
            fibN = fibNminusOne + fibNminusTwo;
            fibNminusTwo = fibNminusOne;
            fibNminusOne = fibN;
        }
        return fibN;
    }

    public static void main(String[] args) {
        System.out.println(Fibonacci(3));
    }
}

题目二：青蛙跳台阶问题
一只青蛙可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上n级台阶总共有多少种跳法。
思路：思想和斐波那契一样，第一次为1种，第二次为2种，第三次为为第一次和第二次的和，以此类推，很精妙。
解决方案：
public static int jumpStairs(int n){
int[] result = new int[]{0,1};
if (n < 2) return result[n];
int fibNminusOne = 1;
int fibNminusTwo = 1;
int fibN = 0;
for (int i=2; i<=n; i++){
fibN = fibNminusOne + fibNminusTwo;
fibNminusTwo = fibNminusOne;
fibNminusOne = fibN;
}
return fibN;
}