C++算法 —— 动态规划（7）两个数组的dp_动态规划数组怎么列

---

每一种算法都最好看完第一篇再去找要看的博客，因为这样会帮你梳理好思路，看接下来的博客也就更轻松了。当然，我也会尽量在写每一篇时都可以不懂这个算法的人也能边看边理解。

1、动规思路简介

动规的思路有五个步骤，且最好画图来理解细节，不要怕麻烦。当你开始画图，仔细阅读题时，学习中的沉浸感就体验到了。

状态表示
状态转移方程
初始化
填表顺序
返回值

动规一般会先创建一个数组，名字为dp，这个数组也叫dp表。通过一些操作，把dp表填满，其中一个值就是答案。dp数组的每一个元素都表明一种状态，我们的第一步就是先确定状态。

状态的确定可能通过题目要求来得知，可能通过经验 + 题目要求来得知，可能在分析过程中，发现的重复子问题来确定状态。还有别的方法来确定状态，但都大同小异，明白了动规，这些思路也会随之产生。状态的确定就是打算让dp[i]表示什么，这是最重要的一步。状态表示通常用某个位置为结尾或者起点来确定，但两个数组的问题则不是这样，要选取第一个字符串[0, i]区间以及第二个字符串[0, j]区间作为研究对象。

状态转移方程，就是dp[i]等于什么，状态转移方程就是什么。像斐波那契数列，dp[i] = dp[i - 1] + dp[i - 2]。这是最难的一步。一开始，可能状态表示不正确，但不要紧，大胆制定状态，如果没法推出转移方程，没法得到结果，那这个状态表示就是错误的。所以状态表示和状态转移方程是相辅相成的，可以帮你检查自己的思路。

要确定方程，就从最近的一步来划分问题。

初始化，就是要填表，保证其不越界。像第一段所说，动规就是要填表。比如斐波那契数列，如果要填dp[1]，那么我们可能需要dp[0]和dp[-1]，这就出现越界了，所以为了防止越界，一开始就固定好前两个值，那么第三个值就是前两个值之和，也不会出现越界。初始化的方式不止这一点，有些问题，假使一个位置是由前面2个位置得到的，我们初始化最一开始两个位置，然后写代码，会发现不够高效，这时候就需要设置一个虚拟节点，一维数组的话就是在数组0位置处左边再填一个位置，整个dp数组的元素个数也+1，让原先的dp[0]变为现在的dp[1]，二维数组则是要填一列和一行，设置好这一行一列的所有值，原先数组的第一列第一行就可以通过新填的来初始化，这个初始化方法在下面的题解中慢慢领会。

第二种初始化方法的注意事项就是如何初始化虚拟节点的数值来保证填表的结果是正确的，以及新表和旧表的映射关系的维护，也就是下标的变化。

填表顺序。填当前状态的时候，所需要的状态应当已经计算过了。还是斐波那契数列，填dp[4]的时候，dp[3]和dp[2]应当都已经计算好了，那么dp[4]也就出来了，此时的顺序就是从左到右。还有别的顺序，要依据前面的分析来决定。

返回值，要看题目要求。

这篇博客需要从头开始看，后面的题会用到前面的思路。

2、最长公共子序列

1143. 最长公共子序列

确定状态。让dp[i][j]表示s1的[0, i]区间以及s2的[0, j]区间内所有的子序列中，最长公共子序列的长度。

如果s1和s2最后一个字符相同，那么最长公共子序列一定是以这个字符为结尾的。如果公共子序列在s1和s2内部，那么再连接最后一个字符才是最长公共子序列；如果s1的公共子序列从某个字符到最后一个字符，而s2的公共序列在内部，那么既然是公共序列，最后一个字符一定相同，那么s2就可以连接最后一个字符。

i和j从字符串的末尾开始，如果s[i] == s[j]，那么只需要在0 ~ i - 1和0 ~ j - 1找到公共子序列，然后+1就可。如果s[i] != s[j]，那么最长公共子序列一定不以这两个字符结尾，这样的话我们就可以在s1的[0, i - 1]和s2的[0, j]里找公共子序列，或者[0, i]，[0, j - 1]，或者[0, i - 1]和[0, j - 1]，也就是3种情况，实际上前两个包含最后一个情况[0, i - 1]，[0, j - 1]，但不干扰最后最后结果，因为我们要的是最长长度，重复的问题不需要考虑，只要能保证不漏掉情况就行，只是还是可以优化，就不去考虑第三种情况。如果题目要求求最长公共子序列个数，那么第3种情况肯定要去掉，因为已经包含了。

初始化。空串是有研究意义的，因为空串也是公共子序列，只是长度为0，并且因为空串的存在，也方便初始化。 二维数组dp表，多添加一行一列，让原先的[0][0]变成现在的[1][1]，现在的第一行表示s1为空的情况，第一列表示s2为空的情况。为了保证添加的一行一列的值保证后续填表是正确的，以及下标的映射关系，我们对于字符串可以在最前面加个空字符就行。

填表顺序，因为需要i - 1，j - 1，所以从上到下，每一行从左到右。返回值是最大值，也就是dp表右下角的值。

    int longestCommonSubsequence(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        s1 = " " + s1, s2 = " " + s2;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;//如果前面没有加那个空字符，那么这里就得些s1[i - 1] == s2[j - 1]，保证下标对齐
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、不相交的线

1035. 不相交的线

这道题建立在公共子序列的思路基础上。不交叉的线，也就是上面选中的数字的顺序，下面选中的数字也得按照这个顺序选中，这样就可以保证符合要求。其实这就是在找公共子序列的问题，序列中的元素可以不连续，但顺序不会变，左边的元素都比右边元素靠前，所以这道题就转化为了最长公共子序列的长度。

定义dp[i][j]为nums1里的[0, i]区间以及nums2里的[0, j]区间里面的所有的子序列中，最长公共子序列的长度，因为题目要求求长度。按照公共子序列的思路，可以分为两种情况，n1[i] == n2[j]，两个数字相等，那就找dp[i - 1][j - 1]，因为这里存的是n1到第i - 1个数字，n2到第j - 1个数字的最长的公共子序列，然后 + 1就是dp[i][j]应当存的值。如果n1[i] != n2[j]，那么就转换为三种情况，找到do[i - 1][j]，dp[i][j - 1]，dp[i - 1][j - 1]的最大值当作dp[i][j]的值，因为前两个包含了dp[i - 1][j - 1]的情况，所以只考虑前两个。这样dp表的填写就完成了。

由于我们需要i - 1，j - 1，所以在原本的dp表左上角加上一行一列，里面的数字要保证不影响后续的填表以及下标的映射关系，之前[0, 0]变成了[1, 1]，所以新增的行列里的值都变成0，因为我们要取最大值，所以这样就不影响。填表顺序是从上到下，从左到右。返回值是dp[n1][n2]。

    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

4、不同的子序列

115. 不同的子序列

根据题目要求，得在s中找t。由于是子序列，所以不必让t完整地出现，看看示例就明白了。既然是子序列，按照之前的思路，我们还是得看看最后一个元素的情况，以及需要用到dp表中前面的值。

先定义dp[i][j]表示s的[0, j]区间内的所有子序列中，有多少个t的[0, i]区间内的子串。注意一个是子序列，一个是子串，这两个的含义需要分清，一个不需要连续，一个必须连续的字符。接下来确定状态转移方程。s的子序列中有两个情况，包含s[j]和不包含。如果包含s[j]，要是想包含t[0, i]区间的子串，就得让s[j] == t[i]才可行，这两个字符相等了，那就再找dp[i - 1][j - 1]，不需要 + 1，因为求的是个数，不是长度。如果不包含s[j]，那么就往前一步，变成[0, j - 1]里找t，也就是dp[i][j - 1]。因为找的是个数，所以dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]。

初始化的时候，因为有i - 1和j - 1，新增一行列比较好，新增在左上角。第一行，代表dp[0][j]，也就是说t是空串，那么这一行应当都初始化为1，因为肯定包含空串；第一列，dp[i][0]，s是空串，那么就不包含t了，应当初始化为0，而dp[0][0]这个位置，两个都是空串，应当为1，这点在上面初始化第一行时就做好了。填表顺序是从上到下，从左到右。返回值就是dp[m][n]。

    int numDistinct(string s, string t) {
        int m = t.size(), n = s.size();
        vector<vector<double>> dp(m + 1, vector<double>(n + 1));//long和long long都不行，溢出
        for(int j = 0; j <= n; j++) dp[0][j] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] += dp[i][j - 1];
                if(t[i - 1] == s[j - 1]) dp[i][j] += dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5、通配符匹配

44. 通配符匹配

像abcde和ae这样，星号匹配空字符，星号匹配bcd都是可以的。

根据经验，两个字符串分别选取[0, i]和[0, j]区间。题目中是能否匹配成功，那么我们就定义dp[i][j]是p[0, j]区间的子串能否匹配s[0, i]区间内的子串，类型是bool。

状态转移方程。还是根据最后一个位置的状况来确定问题。因为是通配符，每个位置都有三种情况。如果最后一个位置是普通字符，那么如果p[j] == s[i]，就看dp[i - 1][j - 1]是否为true；如果最后一个位置是?，它可以直接匹配一个字符，然后再看dp[i - 1]
[j - 1]；如果最后一个位置是星号，星号可以匹配很多种，匹配空字符，就看dp[i][j - 1]，匹配1个字符，就看dp[i - 1][j - 1]，匹配2个字符，就看dp[i - 2][j - 1]。星号的情况如何实现到代码上？dp[i][j] = dp[i - 0][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1]，如果i变为i - 1，那么dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1]，所以可以发现dp[i][j]就等于dp[i][j - 1] || dp[i - 1][j]，后面的所有情况都包含在dp[i - 1][j]中。

初始化，因为有i - 1，j - 1，我们就需要在左上角新增一行一列。新增行列的初始化需要做一下分析，第一个位置dp[0][0]，空串匹配空串，这肯定是true；第一列表示dp[i][0]，p是空串，那它不能匹配字符串，所以第一列除了第一个元素，其它都是false；第一行，也就是dp[0][j]，s是空串，p只有是星号才能是true，不是的话就是false。下标映射关系也需要分析一下，我们可以按照之前的做法，下标减1，而因为是字符串，也可以在字符串之前加一个空字符。

填表顺序是从上到下，从左到右。返回值就是右下角那个值。

    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s = " " + s, p = " " + p;
        dp[0][0] = true;
        for(int j = 1; j <= n; j++)
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(p[j] == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

6、正则表达式匹配

10. 正则表达式匹配

这里的星号和上一个题不一样，星号不能连续，任意一个字符搭配星号可以变成空串。还是选取s[0, i]区间，p[0, j]区间。dp[i[j]表示p[0, j]区间内的子串是否能够匹配s[o, i]区间内的子串，所以是bool。

状态转移方程。还是根据最后一个位置的状态来分析。先看最后一个位置，如果p[j] == s[i]，那就看dp[i - 1][j - 1]是否为true，那么dp[i][j]就是true；如果p[j]是点号，那肯定没问题；如果是星号，它得看前面一个值，前面是点号，那么这两个字符可以转换成0个以及多个点号，空串就得看dp[i][j - 2]，一个点号就看dp[i - 1][j - 2]，转换成2个点号就是dp[i - 2][j - 2]，以此类推，只要有一个为true，那么dp[i][j]就是true，dp[i][j]是这样，那么dp[i - 1][i]也能表示出来，所以最后能得到dp[i][j] = dp[i][j - 2] || dp[i - 1][j]。如果p[j]是星号，p[j - 1]是普通字符，那么有两种情况，可以匹配成空串，那就看dp[i][j - 2]，如果匹配一个，也就是p[j - 1]和s[i]相等的话，再就看dp[i - 1][j]是否为true。

所以方程应当是这样的：p[j] == s[i]或者p[j]是一个点，那就看dp[i - 1][j - 1]是否true，dp[i][j]才为true。如果p[j]是星号，有两种大情况，每个情况都有匹配成空串的情况，都是dp[i][j - 2]，以及还要看是点还是普通字符，再看dp[i - 1][j]。

初始化时最前面引入空串，新增行列，管理好下标的映射关系。dp[0][0]是true，第一列其余部分就是false，因为第一列表示p是空串，这肯定不能匹配；第一行是s为空串，p可以任意一个字符搭配星号，多个这样的组合也行，只要偶数位置是星号就行。

填表顺序是从上到下，从左到右。返回值是dp[m][n]。

    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s = ' ' + s, p = ' ' + p;
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2)
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(p[j] == '*') 
                    dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
                else dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

7、交错字符串

97. 交错字符串

s3是由s1和s2中的序列构成的，长度等于这两个字符串之和。为了能让分析更清楚，三个字符串前面都加上一个空字符，这样就是s1[1, i]，s2[1, j]，s3[1, i+j]区间做分析。

把dp[i][j]表示为s1[1, i]区间内的字符串以及s2[1, j]区间内的字符串能否拼接凑成s3[1, i+j]区间内的字符串，类型就是bool。

状态转移方程。根据最后一个位置来分析。如果s3[i + j]处的结尾字符有可能是s1的，也有可能是s2的，所以分为两种情况，如果是s1，如果s1[i] == s3[i + j]，那么就看dp[i - 1][j]是否为true，s2也同理，看dp[i][j - 1]是否为true。

初始化时，在左上角新增一行一列，dp[0][0]，也就是3个字符串都为0，就是true。第一列，也就是s2为空时，dp[i][0]，就看s1和s3之间哪个位置字符相同，哪个就是true，不是就之后所有位置都是false；第一行也是如此，比较s2和s3。填表顺序是从上到下，从左到右。返回值是dp[m][n]。

    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if(m + n != s3.size()) return false;
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for(int j = 1; j <= n; j++)
        {
            if(s2[j] == s3[j]) dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            if(s1[i] == s3[i]) dp[i][0] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

8、两个字符串的最小ASCII删除和

712. 两个字符串的最小ASCII删除和

仔细分析示例会发现，两个字符串有多种删除法，得到不同的结果字符串，但是删除的字符的ASCII码值最小的结果，是s1和s2中的公共子序列，并且还是ASCII值最大的那个，所以这个问题就变成了找公共子序列中ASCII值最大的。

让dp[i][j]表示s1的[0, i]区间以及s2的[0, j]区间内的所有的子序列里，公共子序列的ASCII最大和。

状态转移方程。看最后一个位置来分析，如果s[i] == s[j]，那么就看dp[i - 1][j - 1]，然后再加上这个位置的值即可；如果不相等，那么就变成两种情况，s1以i - 1位置结尾来分析dp[i - 1][j]和s2以j - 1位置为结尾来分析dp[i][j - 1]。

初始化时，左上角新增一行一列，要管理好下标的映射关系，新增行列初始化为0。

填表顺序是从上到下，从左到右。最大值是dp[m][n]，然后用2个字符串的ASCII和来减去两倍的dp[m][n]，因为两个字符串都要减。

   int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m ; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if(s1[i - 1] == s2[j - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);
            }
        }
        int sum = 0;
        for(auto s : s1) sum += s;
        for(auto s : s2) sum += s;
        return sum - (2 * dp[m][n]);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

9、最长重复子数组

718. 最长重复子数组

如果以[0, i]区间来分析，找子数组，这个角度就不行，因为子数组和子序列不同，它必须是连续的，[0, i]区间内的最长子数组可能不以i结尾，而是以前面的某个位置结尾，所以就无法确定最长长度。这题的状态表示应当改为dp[i][j]是nums1中以i位置元素为结尾的所有子数组和nums2中以j位置元素为结尾的所有子数组中最长重复子数组的长度。

状态转移方程。以最后一个位置来分析。如果nums1[i] != nums[j]，那此时就不是重复的子数组，如果相等的话，结尾位置就没问题了，那就再看前面一个位置，所以应当是dp[i - 1][j - 1] + 1。

初始化时，新增一行一列，注意下标的映射关系，新增的行列应当全为0。

填表顺序是从上到下，从左到右。返回值是最大值。

    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        int ret = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j<= n; j++)
            {
                if(nums1[i - 1] == nums2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结束。