【算法】动态规划 Dynamic Programming

由《算法导论》，动态规划适用于解决具有以下性质的问题：最优子结构性质（其中包含子问题无关性质，也即无后效性），以及子问题重叠性质。

最优子结构性质

最优子结构性质有两个要求，其一为：问题的最优解可以由相关子问题的最优解组合而成。因为动态规划解决问题的方式是逐渐降低问题的规模，也就是将相对复杂的问题分解为若干子问题，再通过子问题的最优解组合去得到复杂问题的最优解，即我们必须能够组合，并且知道怎么组合（一般取决于实际问题）子问题最优解去得到最终的最优解。

一个经典的例子就是无权有向图的最短路径问题。假设要求出从A点到B点（A和B不是同一点）的最短路径，我们可以取出该最短路径 中的一中间点C，并断言路径中 和 这两部分，一定分别是从A点到C点的最短路径和从C点到B点的最短路径。即：从A到B的最短路径（复杂问题的最优解），由从A到C的最短路径（子问题的最优解）和从C到B的最短路径（子问题的最优解）组合得到，这就是最优子结构性质。

证明很简单，假设存在从A到C的一条更短的路径 ，我们可以用这条更短路径去替换 ，所得到的新的路径 ，其长度必定小于 ，而这与 最短矛盾。

在实际编程中，因为我们尚不知道最短路径，故也不知道C点是哪个点，所以我们是反过来，对每一个可能的中间结点C，都去求出对应的 和 ，然后取出它们长度之和最小的那一个，就是我们所要的那个点了。

子问题无关性质

最优子结构性质的另外一点，即子问题可以独立求解，或者说两个子问题是无关的。另一个说法是无后效性，即一个子问题的求解，不会影响后面子问题的求解。在上面的例子中，在最短路径 中，求最短路径 和 这两个过程一定是无关的，即求A到C的最短路径时，一定不影响求C到B的最短路径。这是因为，求 时，我们只关注C点以及之后将会遇到的点，至于我们怎么到达C点的，在求解时根本不会有任何作用。

严谨地说，我们可以断言， 和 中除了C点，不会再有其他公共的点。证明很简单，假设存在另一个公共点D，那么有 和 ，此时取路径 ，显然它比 更短，于是矛盾。这说明这两条最短路径其实并不共享任何点（除了C点，但C点无关紧要），所以它们的求解一定是无关的。

子问题无关性质，保证了当全局最优时，其所有子问题本身的解法，一定和我们求出的最优解一致。可以想象，如果子问题的求解是有关的，那么我们求出的子问题的最优解可能是互相矛盾的，取组合起来不一定是有效的解，更别说是不是全局最优解了。

最优解递推关系

在确保题目满足最优子结构性质后，接下来的一步就是确定最优解的递推关系，即子问题的最优解如何组合成全局最优解，该递推关系也称作状态转移方程。下面举一些例子：

LeetCode 62. 不同路径

这个问题要求解的是矩阵中左上角到达右下角的不同路径总数，且只能往下走或往右走。这个问题满足最优子结构性质，假设以 表示从左上角 (1, 1) 到达 (x, y) 的路径数量，在非平凡的情况下（即不考虑边界）显然有：

这就是这个问题的状态转移方程。由递推式可知，如果我们从左往右，从上往下依次求出 dp，那么递推式中右边的总是已知的。但我们必须知道最开始的值是多少，才能从左往右从上往下不断地求，在这个问题里很简单，即：

也就是说，在求状态转移方程时，我们无需担心右边要怎么去求，而是总假定右边总是已知的，因为在递推式的作用下，右边的问题也会被继续分解，直到变为最简单的情况。

C#实现代码如下：

public class Solution {
    public int UniquePaths(int m, int n) {
        int[,] dp = new int[m + 1, n + 1];
        dp[1, 1] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == 1 && j == 1) continue;
                if(i == 1)
                {
                    dp[i, j] = dp[i, j - 1];
                }
                else if(j == 1)
                {
                    dp[i, j] = dp[i - 1, j];
                }
                else
                {
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
                }
            }
        }
        return dp[m, n];

    }
}

上面这道题最好的解法并不是动态规划，但很简单地展现了动态规划的递推思想。需要注意的是，在动态规划中，子问题的解总是被储存起来的（一般用数组，例如上面例子中的dp），这样做的好处需要对比下面这种解法：

在这里我们使用了函数递归，其关系和上面的状态转移方程是一样的。但是在效率上，它们却差得多。在这个问题中，如果使用递归算法，求解的过程相当于一棵二叉树，每个点都需要调用两次递归函数，即每个结点都有两个分支，以此类推，直到遇到边界。这样的时间复杂度是指数级别的，因为在求解的过程中，有很多点都被重复的计算了（它同时作为多个点的上边或左边的点）。但在动态规划算法中，每一个点只会被求解一次，求解后就储存在数组中，下次使用时直接调用即可，这样的时间复杂度是多项式级别的。同个子问题的解被多次使用，这就是下面要讲的子问题重叠性质。

子问题重叠性质

子问题的求解是无关的，又是重叠的。实际上这并不矛盾。子问题无关是指无后效性，即一个子问题的求解过程不影响其他子问题的求解过程（尽管它们的解存在递推关系），而子问题重叠，是指同个子问题的解在解决其他子问题时被反复使用。

在递归算法中，问题是自顶向下解决的，子问题在递归过程中可能被反复计算。一个降低时间复杂度的的办法就是加上一个“备忘录”，记录已经解决的子问题的解，这种方法也叫记忆化搜索。伪代码如下：

使用“备忘录”，可以将指数时间复杂度降低到多项式时间复杂度，本质上就是动态规划的思想，但是在效率上由于频繁的函数调用所以不如自底向上的动态规划算法。

动态规划算法能提升多少效率，一定程度上由子问题的重叠性质决定，重叠得越多，效率提升就越高。另外的因素还有状态转移方程，一个问题可能有多种状态转移方程，所产生的子问题空间是不一样的。

零钱兑换问题

LeetCode 322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

这是个经典的动态规划问题，一个常见的错误解法是贪心算法，例如使用面额为1，5，11的硬币去凑15，贪心算法的结果是11 + 1 + 1 + 1 + 1，而正确的结果是5 + 5 + 5。

使用暴力的话时间复杂度太高，故考虑动态规划。可以发现这个问题是满足最优子结构的，设凑出 元所需的最少硬币个数是 ，则

，其中 取遍所有小于等于 的面额。

并且我们有初始值 。而对于那些比所有面额都小的金额，显然是无解的。

所以我们如果按 从小到大（直到amount）求解 ，那么递推式右边总是已知的。代码就出来了：

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int n = coins.Length;
        int[] dp = new int[amount + 1];
        dp[0] = 0; //初始值
        for(int i = 1; i <= amount; i++)
        {
            dp[i] = int.MaxValue;
            bool flag = false; //表示是否有解
            for(int c = 0; c < n; c++)
            {
                //只取小于等于i的面额，且i - coins[c]必须有解
                if(i < coins[c] || dp[i - coins[c]] == -1)
                {
                    continue;
                }
                dp[i] = Math.Min(dp[i], dp[i - coins[c]] + 1);
                flag = true; //至少有一个解
            }
            if(!flag)
            {
                dp[i] = -1; //无解
            }
        }
        return dp[amount];
    }
}