动态规划简介

什么是动态规划

动态规划(Dynamic Programming, DP)是一种解决递归问题的方法，和递归相比，DP更高效些。使用递归问题的时候，我们其实是不断重复的解决子问题。在DP中，我们把子问题的解法保存下来，这样可以避免不必要的重复(这种做法也就是Memoization)。

DP和memoization是一套组合拳，所以，一般使用DP解决问题的时候，都包含两部分：

Recursion(递归)：递归的解决子问题；
Memoization(缓存): 将子问题的解缓存起来，避免重复计算；

以Fibonacci数列为例：

Fibonacci数列的定义：这个数列从第3项开始，每一项都等于前两项之和。我们用数学的方式来定义：

Fibonacci(N):
F(0) = 1;
F(1) = 1;
F(n) = F(n-1) + F(n-2), n > 1;

使用递归来解：

public int fibonacciRec(int n) {
    if (n == 0 || n == 1) {
        // 0 for 0, and 1 for 1
        return n;
    }
    return fibonacciRec(n - 1) + fibonacciRec(n - 2);
}

结合上图可以看出，当计算Fibonacci(4)时，需要计算Fibonacci(3)和Fibonacci(2)，计算Fibonacci(3)的时候，需要计算Fibonacci(2)和Fibonacci(1)，可以看到这里Fibonacci(2)被计算了两次。使用递归解决问题时，相同的子问题，会被重复的求解。

递归解法的时间复杂度: T(n) = T(n-1) + T(n-2) + 1 = O(2^n)

使用DP+Memoization

还是那句话：将子问题的结果缓存下来，减少重复的计算。所以在求解的过程中，检查缓存中是否已经有了该子问题的解，若有直接使用，若无计算并缓存。

public int fibonacciDP(int n) {
		if (n <= 1) return n;
    int fibN[] = new int[n + 1];
    fibN[0] = 0;
    fibN[1] = 1;
    for (int i = 2; i <= n; i++) {
        fibN[i] = fibN[i - 1] + fibN[i - 2];
    }
    return fibN[n];
}

这个解法的时间复杂度O(n),空间复杂度O(n)。典型的空间换时间的解法，我们对比下在n=20的情况下的耗时对比：

@Test
public void test() {
    Fibonacci fibonacci = new Fibonacci();
    long start = System.nanoTime();
    String ret = "----fibonacciRec(30)=" + fibonacci.fibonacciRec(30);
    ret += ",cost " + ((System.nanoTime() - start)/ 1000) + "us";
    System.out.println(ret);

    start = System.nanoTime();
    ret = "----fibDP(30)=" + fibonacci.fibonacciDP(30);
    ret += ",cost " + ((System.nanoTime() - start) / 1000) + "us";
    System.out.println(ret);
}

在我的电脑上的输出：

----fibonacciRec(30) =832040,cost 8634us
----fibonacciDP(30)  =832040,cost 11us

N越大对比越明显。

DP的两个关键属性：

在判断一个问题是否可以使用DP来解的时候，我们从两个方面来分析，如果一个问题具备这两个属性的话，就可以使用DP来解决:

Overlapping SubProblems, 重叠的子问题求解；
Optimal Substructure, 即最优子结构；

重叠的子问题求解

在上面使用递归求解Fibonacci数列的时候，已经提到，以求解Fibonacci(4)为例，需要计算F(3) 和F(2)，对两者结果求和；而计算F(3)的时候，又会将F(2)计算一次。重叠的子问题带来的问题就是计算的浪费，时间复杂度很高，在我的电脑上，递归解法求解F(50)已经是个超级耗时的计算，而DP法只需要30us。

----fibonacciRec(50) =-298632863,cost 62230537us, 
----fibonacciDP(50)  =-298632863,cost 34us

最优子结构

如果一个问题，可以拆分成若干个子问题，通过对子问题求最优解，从而得到整个问题的最优解，那么我们就说这个问题满足最优子结构。

「真诚赞赏，手留余香」