第一个数是1，第二个数也是1，从第三个数开始，后面每个数都等于前两个数之和。要求：输入一个n，输出第n个斐波那契数。

还是我们上节讨论递归与分治策略时候举的第一个例子——Fibonacci数列问题，它实在太经典了，所以将其反复拿出来说。

我们如果深入分析一下上节说过的递归方法解决Fibonacci数列，就会发现出现了很多重复运算，比如你在计算f(5)的时候，你要计算f(4)和f(3),计算f(4)又要计算(3)和f(2),计算f(3)，又要计算f(2)和f(1),看下面这个图

对f(3)和f(2)进行了重复运算，这还是因为5比较小，如果要计算f(100),那你可能要等到天荒地老它还没执行完

    public static int simFibonacci(int n) {
        if (n == 1) return 1;
        else if (n == 2) return 1;
        else return simFibonacci(n - 1) + simFibonacci(n - 2);
    }

上面就是递归的解法，代码看着很简单易懂，但是算法复杂度已经达到了O(2^n),指数级别的复杂度，再加上如果n较大会造成更大的栈内存开销，所以非常低效。

DP策略解决这个问题

我们知道导致这个算法低效的根本原因就是递归栈内存开销大，对越小的数要重复计算的次数越多，那既然我们已经将较小的数，诸如f(2),f(3)……这些计算过了，为什么还要重复计算呢，这时就用到了DP策略，将计算过的f(n)保存起来。我们看看代码：

   //使用数组记录前100个斐波那契数
    static int[] arr = new int[100];

    public static int fibonacci(int n) {
        if (n == 1) return 1;
        else if (n == 2) return 1;
        else {
            if (n <= 100 && arr[n] != 0) {
                return arr[n];
            } else {
                arr[n] = simFibonacci(n - 1) + simFibonacci(n - 2);
                return arr[n];
            }
        }
    }