动态规划（一）

动态规划其实和递归或者分治没有根本上的区别（关键是看有无最优子结构）
共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解

讲到动态规划，就不得不提到一个经典的问题——斐波那契数列。
注：有些地方会要求答案取模 1e9+7（1000000007），这里就不考虑这个问题啦。
如果不使用动态规划，直接递归的话，代码可以是这样的

    public static int fib(int n) {
        return n <= 1 ? n : fib(n - 1) + fib(n - 2);
    }

这样的情况下，算法的时间复杂度达到了指数级，效率很低，因为它进行了很多重复性的计算。所以我们就自然而然的想到了，那能否不做这些重复性的计算呢？答案是可以的。我们可以使用一个数组，来存储我们计算出来的数据。当需要再次计算这个值的时候，直接从数组中拿就好了，算是一种空间换时间的记忆化搜索吧。

public static int fib(int n,int[] memo) {
        if (n<=1) return n;
        if (memo[n] == 0) {
            memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
        }
        return memo[n];
    }

这样算法的时间复杂度就变成了O(n)，从指数级转变成了线性的，算法的效率大大提高了！
那能否继续优化这个算法呢？答案依然是可以的，其实人脑对于这种问题很多时候会采用自顶向下的递推，什么意思呢？比如说：你要计算fib(6)的值，那你可能会想，要计算fib(6)就要先算fib(5)和fib(4)，要算fib(5)和fib(4)又要先算fib(3)和fib(2)......这就是自顶向下的递推，那我们可以换一种思路，自底向上进行递推，从fib(0)和fib(1)递推到fib(n)，也就解决了问题，代码是这样的：

public static int fib(int n,int[] dp) {
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

这就是动态规划的最简单的应用。