【算法】动态规划 Dynamic Programming

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

最优子结构性质

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

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

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

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

子问题无关性质

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

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

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

最优解递推关系

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

LeetCode 62. 不同路径

这个问题要求解的是矩阵中左上角到达右下角的不同路径总数，且只能往下走或往右走。这个问题满足最优子结构性质，假设以 \( dp[x, y] \) 表示从左上角 (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。

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

\( F(X) = min\{ F(X - Y) + 1 \} \)，其中 \(Y\) 取遍所有小于等于 \(X\) 的面额。

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

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

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];
    }
}

最长回文子串

LeetCode 5. 最长回文字串

给定字符串s，找出s当中最长的回文子串。

这是个字符串对象的动态规划问题，涉及字符串的子串问题通常都需要创建一个二维的DP数组，常规的设置方法为dp[i, j]表示字符串中索引从i到j的子串关于该问题的答案（bool类型），此时dp[i, i]表示单个字符的子串，另一种设置方法为dp[i, j]表示字符串中从索引i开始且长度为j的子串关于该问题的答案，此时dp[i, 1]表示单个字符的子串，dp[i, 0]表示空串。下面采取第一种设置方法。

对于回文子串问题，最优子结构性质在于如果dp[i, j]是一个回文子串，那么dp[i + 1, j - 1]也是一个回文子串，这启发最优解递推关系：如果dp[i + 1, j - 1]是一个回文子串，且索引i处的字符和索引j处的字符相同，那么dp[i, j]也是一个回文子串。即：

注意我们总是从长度较小的子串递推到长度较大的子串，因此DP数组的填充是按长度从小到大进行的，假设字符串s的长度为n。为了使索引有效，上述递推式必须满足\( 0 \leq i + 1,i,j,j - 1 \leq n - 1 \, and \, i + 1 \leq j - 1\)。

初始解是显然的，任何单个字符的子串都是回文子串，任何连续两个相同字符的子串都是回文子串。

public class Solution {
    public string LongestPalindrome(string s) {
        int n = s.Length;
        bool[,] dp = new bool[n, n];
        int maxs = 0, maxe = 0;
        for(int i = 0; i < n; i++)
        {
            dp[i, i] = true;
        }
        for(int l = 2; l <= n; l++)
        {
            for(int i = 0; i + l - 1 < n; i++)
            {
                int j = i + l - 1;
                if(s[i] != s[j])
                {
                    dp[i, j] = false;
                }
                else if(l <= 3)
                {
                    dp[i, j] = true;
                }
                else
                {
                    dp[i, j] = dp[i + 1, j - 1];
                }
                if(dp[i, j])
                {
                    maxs = i;
                    maxe = j;
                }
            }
        }
        return s[maxs..(maxe + 1)];
    }
}

最长回文子序列

LeetCode 526. 最长回文子序列

此题和上一题类似，但要求的是子序列而不是子串，思路是一致的，但有一些微妙的区别。

设dp[i, j]表示索引从i到j的子串的最长回文子序列的长度，以回文串的性质可知，如果索引i处的字符和索引j处的字符相同，那么\(dp[i, j] = dp[i + 1, j - 1] + 2\)，否则索引i和索引j不能同时作为回文子序列的头和尾，于是\(dp[i, j] = max\{dp[i + 1, j], dp[i, j - 1]\}\)。

编辑距离

LeetCode 72.编辑距离

给你两个单词word1和word2，返回将word1转换成word2所需的最少操作数，你可以对word1和word2执行如下操作：插入一个字符、删除一个字符、替换一个字符。

这道题提供了三种操作，因此问题空间很复杂，需要先对问题进行化简：注意到对word1插入一个字符和对word2删除一个字符是等价的，反之亦然，对word1替换一个字符和对word2替换一个字符是等价的，因此题目中的6种操作可以化简为3种：对word1插入一个字符，对word2插入一个字符（这相当于对word1删除一个字符，但只有插入和替换会更好处理），对word1替换一个字符。

注意到插入和替换的顺序是不重要的，因此限制在末尾进行插入和替换，并不影响问题的求解。由于操作的等价性，以任何方式将word1转换为word2或者将word2转换为word1的最少操作数是相同的，因此方向是无所谓的，即编辑距离不受操作对象的影响。

可设dp[i, j]为word1前i个字母和word2前j个字母之间的编辑距离，这个设置很巧妙，如果设置dp[i, j]为word1中直到索引i的前缀和word2直到索引j的前缀之间的编辑距离，对空串的表达会比较吃力，而在这道题中空串是很重要的：如果A是空串，那么A和B之间的编辑距离为Length(B)。在这样的设置下，DP数组两个维度的长度分别是n + 1和m + 1，其中n和m分别是word1和word2的长度。

初始解为\(dp[i, 0] = dp[0, j] = 0\)。

分别考虑3种操作，对于dp[i, j]，有如下递推关系：

对于dp[i - 1, j]，可通过插入一个字符到达dp[i, j]，即\(dp[i, j] = dp[i - 1, j] + 1\)，同理\(dp[i, j] = dp[i, j - 1] + 1\)。

对于dp[i - 1, j - 1]，如果word1的第i个字母和word2的第j个字母相同，那么无需操作，此时\(dp[i, j] = dp[i - 1, j - 1]\)，否则，可以通过替换一个字符到达dp[i, j]，此时\(dp[i, j] = dp[i - 1, j - 1] + 1\)。

正则表达式匹配

LeetCode 10. 正则表达式匹配

给定字符串s和字符串模式p，实现支持'.'和'*'的正则表达式匹配。

这是道较难的Hard题，可以通过动态规划解决。难点在于'*'的匹配十分复杂，因为'*'的匹配并不具有无前效性，如果从左往右分析会很麻烦，这个时候可以尝试从右往左分析，由于空串在正则表达式匹配中比较重要，因此可以采取和上题类似的设法：dp[i, j]表示字符串s中前i个字符和模式串p中前j个字符是否匹配。

采取从右往左分析，整体的思路：判断字符串s和模式串p的最后一个字符是否匹配，如果匹配那么再观察左侧剩余的子串是否匹配，复杂的地方在于模式串p的最后一个字符可能是特殊字符'.'或'*'。

如果\(s[i - 1]==p[j - 1] || p[j - 1] == '.'\)，说明s[i - 1]和p[j - 1]是匹配的，关键看dp[i - 1, j - 1]是否匹配，此时dp[i, j] = dp[i - 1, j - 1]。

如果s[i - 1]和p[j - 1]不匹配，尚不能确定dp[i, j]不匹配，因为还未考虑模式串中的'*'，如果p[j - 1] != '*'，那么dp[i, j]确实不匹配，否则需要考虑s[i - 1]是否匹配p[j - 2]。如果\((s[i - 1] == p[j - 2] || p[j - 2] == '.') \, and \, p[j - 1] == '*'\)，可以消除模式串中p[j - 2]字符零次、一次或两次以上，此时有如下匹配的方法：

消除零次，此时\(dp[i, j] = dp[i, j - 2]\)。

消除一次，此时\(dp[i, j] = dp[i - 1, j - 1]\)。

消除两次以上，此时\(dp[i, j] = dp[i - 1, j]\)。

由于是从右往左分析，因此对'*'的处理会比较方便（此时具有无前效性），只要根据需要消除字符串s中的字符，如果能够一直消除那就一直保留模式串p中的'*'，直到不能匹配时丢弃模式串中的'*'及其前面的字符。

如果\(s[i - 1] != p[j - 2] \, and \, p[j - 2] != '.' \, and \, p[j - 1] == '*'\)，此时相当于消除零次，即\(dp[i, j] = dp[i, j - 2]\)。

对于初始解，考虑p为空串但s不为空串，此时必定不匹配；如果s为空串但p不为空串，此时匹配的唯一方法是模式串中'*'消除了前面所有的字符；如果s和p均为空串，此时匹配。

public class Solution {
    public bool IsMatch(string s, string p) {
        int slen = s.Length;
        int plen = p.Length;
        bool[,] dp = new bool[slen + 1, plen + 1];
        dp[0, 0] = true;
        for(int i = 1; i <= slen; i++)
        {
            dp[i, 0] = false;
        }
        dp[0, 1] = false;
        for(int j = 2; j <= plen; j++)
        {
            if(p[j - 1] == '*') dp[0, j] = dp[0, j - 2];
            else dp[0, j] = false;
        }

        for(int i = 1; i <= slen; i++)
        {
            for(int j = 1; j <= plen; j++)
            {
                if(p[j - 1] != '*')
                {
                    if(s[i - 1] == p[j - 1] || p[j - 1] == '.')
                    {
                        dp[i, j] = dp[i - 1, j - 1];
                    }
                    else
                    {
                        dp[i, j] = false;
                    }
                }
                else
                {
                    //assert j >= 2
                    if(s[i - 1] == p[j - 2] || p[j - 2] == '.')
                    {
                        dp[i, j] = dp[i, j - 2] 
                        || dp[i - 1, j - 2]
                        || dp[i - 1, j];
                    }
                    else
                    {
                        dp[i, j] = dp[i, j - 2];
                    }
                }
            }
            
        }

        return dp[slen, plen];
    }
}

最长重复子数组

LeetCode 718. 最长重复子数组

给定两个整数数组nums1和nums2，返回两个数组中公共的长度最长的子数组的长度。

此题所要求的是最长公共子数组，子数组在nums1和nums2的起始位置是不定的，因此暴力枚举的话时间复杂度为\(O(n^3)\)。可以使用动态规划方法更快地解决，注意求最长公共子数组相当于求最长公共前缀，枚举nums1和nums2的起始位置i和j，并求出其最长公共前缀的长度LCP[i, j]，不难看出最长公共子数组的长度即为\( Max \{LCP[i, j]\}\)。

所以此题可以归类为LCP问题，而LCP问题是可以使用动态规划求解的，由于LCP[i, j]表示nums1中以i为起始位置且nums2中以j为起始位置的最长公共前缀长度，可知递推关系：

如果\(nums1[i] == nums2[j]\)，则\( LCP[i, j] = LCP[i + 1, j + 1] + 1\)，否则\( LCP[i, j] = 0 \)。

初始解为

\(LCP[n - 1, j] = (nums1[n - 1] == nums2[j])  \, ? \, 1 : 0 \)

\(LCP[i, m - 1] = (nums1[i] == nums2[m - 1]) \, ? \, 1 : 0 \)