用循环的方式求解斐波那契数列

这是《剑指Offer》的第十题 -- 求解斐波那契数列的记录。

题目是这样的：

写一个函数，输入 n，求解斐波那契数列的第 n 项。

很多人一看到这个题，包括我在内，本能的想到的就是递归的解法：

int fib(int n)
{
    if (n < 2)
        return n;
    return fib(n-1) + fib(n-2);
}

因为斐波那契数列本身就是用递归定义的嘛，这样想再正常不过了。但是当我把 上述代码提交到 leetcode 上之后，却告诉我无法通过全部的测试用例，原因是 运行时间超时。一想也是，递归实现的时间复杂度为 O(2^n)，是效率最低的方法。

于是我就想着，怎样把递归用循环改写一下。首先，我想到，递归本质上是栈， 所以我应该用栈来实现。我们可以仿照递归，先把最终需要计算的 fib(n) 入栈。 为了计算 fib(n) ，我们把 fib(n) 出栈，再把 fib(n-1) 和 fib(n-2) 入栈； 然后为了计算在栈顶的 fib(n-2)，我们再把 fib(n-2) 出栈，把 fib(n-3) 和 fib(n-4) 入栈......嗯，道理是这么个道理，可是我怎么表示这些 fib(n-1)， fib(n-2) 之类的啊？所以，用这种方法是行不通了。于是我们只好正着来。往从 0 到 n 的方向考虑。于是我们得出了这种解法：

int fib(int n)
{
    if (n < 2)
        return n;

    int i, p0, p1, ans;

    for (i = 2; i <= n; i++) {
        ans = p0 + p1;
        p0 = p1;
        p1 = ans;
    }
    return ans;
}

时间复杂度为 O(n)，提交之后一次就通过了。

现在想来，这个题提醒自己，把递归改为循环，不一定要用栈，有时，一个方向不行，反着 想想看，说不定问题就会迎刃而解。

以上。