斐波那楔数列

《剑指offer》面试题10（题目一）：求斐波那楔数列的第n项。

题目：写一个函数，输入n，求斐波那楔数列的第n项。斐波那楔数列定义如下：
f（n）= 0； （n = 0）；
f（n）= 1； （n = 1）；
f（n）= f（n - 1）+ f（n - 2） ； （n > 1）;

思路：很容易想到使用递归函数求解。但递归的过程中出现了重复计算，例如求f（4）= f（3）+ f（2）；需要计算f（3）和f（2），而求f（3）又需要计算f（2）+ f（1）；这个过程中f（2）被计算了2遍。出现了重复计算。为了避免重复计算，把已经得到的数列中间项保存起来，下次要计算时，发现如果已经计算过就不用重复计算了。

代码如下：

public int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        int num1 = 0;
        int num2 = 1;
        int temp = 0;
        for (int i = 2;i <= n;i++) {
            temp = num1 + num2;
            num1 = num2;
            num2 = temp;
        }
        return temp;
    }
}