动态规划：两个数组的dp问题（C++）

前言

动态规划往期文章:

1. 动态规划入门：斐波那契数列模型以及多状态
2. 动态规划：路径和子数组问题
3. 动态规划：子序列问题
4. 动态规划：回文串问题

两个数组的dp问题

1.最长公共子序列（中等）

链接：最长公共子序列

• 题目描述
  

• 做题步骤

1. 状态表示
   对于两个数组的dp，采用一维dp是没有办法清晰的表示状态的，故对于两个数组的dp我们通常采用二维数组。
   
   故定义状态表示为dp[i] [j]：s1的[0，i]区间和s2的[0，j]区间之间的最长公共子序列。

2. 状态转移方程
   对s1的[0，i]区间和s2的[0，j]区间，我们分情况讨论：
   (1)s1[i] == s2[j]，我们只需要知道s1的[0，i - 1]区间和s2的[0，j - 1]区间之间的最长公共子序列，然后加一即可，即dp[i] [j] = dp[i - 1] [j - 1] + 1。（比如s1 = "abc"和s2 = “akc”，就是"ab"和"ak"的最长公共子序列加1）
   
   (2)s1[i] != s2[j]，这个这时最长公共子序列⼀定不会同时以s1[i]和s2[j]结尾。
   ①有可能以s2[j]结尾，去s1的 [0, i - 1]以及s2的 [0, j] 区间内找：此时最大长度为dp[i - 1] [j]。（比如s1 = “ack”，s2 = “bc”）
   ②有可能以s1[i]结尾，去s1的[0, i]以及s2的 [0, j - 1] 区间内找：此时最大长度为dp[i] [j - 1]。（比如s1 = “ac”，s2 = “cb”）
   ③也有可能两者都不是结尾，但这个情况是包括在前两个情况中的，一定小于等于前两者。（比如s1 = “acd”，s2 = “aca”）
   故对于(2)情况，dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1])。

3. 初始化

4. 填表顺序
   参照上面的图，填表顺序为行从上到下，每一行从左到右。

5. 返回值
   依据状态表示，返回值为dp[m] [n]（m，n分别为s1、s2长度）。

• 代码实现

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        //处理下标映射
        s1 = " " + s1, s2 = " " + s2;
        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;         
                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
15
16
17
18

2.不同的子序列（困难）

链接：不同的子序列

• 题目描述
  

• 做题步骤

1. 状态表示
   这个题目虽然标的是困难，但是有前面的做题经验其实还好。
   对这种问题，我们采用二维表，定义状态表示为dp[i] [j]：t的[0, j]区间在s的[0, i]区间出现的方案个数。

2. 状态转移方程
   对s的[0，i]区间和t的[0，j]区间，我们分情况讨论：
   (1)s[i] == t[j]：
   ①比如t = "rab"和s = “rabcb”,第一种同时选s[i]、t[j]为结尾，这个时候的方案数为t的[0, j - 1]区间在s的[0, i - 1]区间出现的方案数(ra在rabc中出现的次数)，即dp[i - 1] [j - 1]。
   ②第二种是不同时选s[i]、t[j]为结尾，这个时候的方案数为t的[0, j]区间在s的[0, i - 1]区间出现的方案数(t = "rab"在s的"rabc"中出现的次数)，即dp[i - 1] [j]。
   两种都符合要求：故(1)情况dp[i] [j] = dp[i - 1] [j] + dp[i - 1] [j - 1]
   
   (2)s[i] != t[j]：
   这个时候只有一种选择，即(1)的②情况，故(2)情况dp[i] [j] = dp[i - 1] [j] 。

3. 初始化
   这个题目的初始化和上一题相似，多开一行一列，把多的一行一列当作空串。其中当t为空串时在s中一定有一种方案（s也拿一个空串出来），故初始化第一列为1。

4. 填表顺序
   填表不明白参考第一题，填表顺序为行从上到下，每一行从左到右。

5. 返回值
   依据状态表示，返回值为dp[m] [n]（m，n分别为s、t长度）。

• 代码实现

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        //这个题目中间填表的时候会溢出，而且溢的不是一点点
        //不过溢出的部分不影响结果，用uint即可
        vector<vector<unsigned int>> dp(m + 1, vector<unsigned int>(n + 1));
        s = " " + s, t =  " " + t;  //处理下标映射
        for(int i = 0; i < m; i++)  dp[i][0] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(s[i] == t[j])  //s[i] == t[j]会多一种选择
                    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
15
16
17
18
19

3.通配符匹配（困难）

链接：通配符匹配

• 题目描述
  

• 做题步骤

1. 状态表示
   依据前面的做题经验，我们定义一个二维表，定义状态表示为dp[i] [j]：p的[0, j]区间能否匹配s的[0, i]区间。

2. 状态转移方程
   对s的[0，i]区间和p的[0，j]区间，我们分情况讨论：
   (1)s[i] == p[j]或者p[j] == '?'时，dp[i] [j] = dp[i - 1] [j - 1]，即只要p的[j - 1]区域能和s的[i - 1]区域匹配，p的[0, j]就可以和s的[0, i]匹配。（比如s = “abc”，p = “ab?”）
   
   (2)p[j] == ’ * ’ 的情况，这个时候有三种可能使得p[0, j]和s[0, i]匹配：
   ①p的[0, j]可以和s的[0, i - 1]匹配，p[j] == ’ * ’ 在表示原来的字符串基础上加上s[i]即可，即dp[i - 1] [j]为真dp[i] [j]为真。（比如s = “abc”，p = “a*”，"ab"和"a*"是匹配的）
   ②p的[0, j - 1]可以和s的[0, i]匹配， ’ * ’ 这个时候匹配空串即可，即dp[i] [j - 1]为真dp[i] [j]为真。（比如s = “ab”，p = “ab*”）
   ③p[0, j - 1]匹配和s的[0, i - 1]，p[j] == ’ * ’ 去替换s[i]，但这种情况实际是可以被归于第一种情况的，如果s[0, i - 1]和p[0, j - 1]匹配，那么s[0, i - 1]和p[0 , j]也一定会匹配，这个时候 ’ * ’ 做空字符串，即dp[i - 1] [j - 1]为真 == dp[i - 1] [j]为真。
   
   以上情况只要一个为真dp[i] [j]就为真。

3. 初始化
   和前面一样，为了避免越界以及方便初始化，我们引入空串的概念，多开一行和一列。
   ①其中两者都为空串可匹配，即dp[0] [0] = true。
   
   ②s为空串，p不为空串(第一行除去[0, 0])的时候如果p的[0, j]区间为连续的 ’ * ’ 也是可以匹配空串的，dp[0] [0……j] = true。([0, j]区间表示连续的 ’ * ’ )
   
   ③p为空串，s不为空串(第一列除去[0, 0])，这个时候不可能匹配，第一列除开[0][0]其它都初始化为false。

4. 填表顺序
   填表不明白参考第一题，填表顺序为行从上到下，每一行从左到右。

5. 返回值
   依据状态表示，返回值为dp[m] [n]（m，n分别为s、p长度）。

• 代码实现

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = " " + s, p = " " + p;   //处理下标映射
        //dp[i][j]：p的[0, j]区间能否匹配s的[0, i]区间
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;  
        for(int j = 1; j <=n; j++)  //初始化s为空串，p有连续'*'可匹配的情况
        {
            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 if(s[i] == p[j] || p[j] == '?')
                    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
15
16
17
18
19
20
21
22
23
24
25
26

4.正则表达式（困难）

链接：正则表达式

• 题目描述
  

• 做题步骤

1. 状态表示
   有前面的做题经验，我们定义一个二维表，定义状态表示为dp[i] [j]：p的[0, j]区域能否匹配s的[0, i]区域。

2. 状态转移方程
   这个题目的重点："a*"说明这个部分可以出现多次，也可以出现0次，即a表示空串，所以分析的时候应该把"字符 + "当作一个整体来考虑。
   
   对s的[0，i]区间和p的[0，j]区间，我们分情况讨论：
   (1)s[i] == p[j]或p[j] == ’ . ’ ，只需要p的[0, j - 1]和s的[0, i - 1]匹配即可，即dp[i - 1] [j - 1]为真dp[i] [j]就为真。（比如s = "abc"和p = “ab.”）
   
   (2)p[j] == ’ * ’ 的情况，这个时候有三种可能使得p[0, j]和s[0, i]匹配：
   ①p[0, j - 2]和s[0, i]匹配，后面的"字符+"表示空串。即dp[i] [j - 2]为真dp[i] [j]就为真。（比如s = “abc”，p = “abcg*”，p后面的"g*"可以直接作空串）
   ②p[0, j]和s[0, i - 1]匹配，原本的"字符+"需要多表示一个字符。
   但这里多表示的字符是固定的，也就是说必须满足p[j - 1] == s[i] 或 p[j - 1] == ’ . ’ ，这个多表示的字符才能符合要求。即满足前面条件dp[i - 1] [j]为真dp[i] [j]就为真。
   （比如s = “abbb”，p = “ab*”，其中"ab*"是可以匹配"abb"的，刚好"b*"多表示一个’ b ’ 符合匹配要求。如果s = "abbc"就p就无法匹配s了）
   
   以上情况只要一个为真dp[i] [j]就为真。

3. 初始化
   为了避免越界已经方便初始化，我们引入空串的概念，多开一行一列。
   ①其中两者都为空串可匹配，即dp[0] [0] = true。
   
   ②当s为空串，p不为空串(第一行除去[0, 0])的时候如果p为连续的"字符 + * + 字符 + * ……"，让这些"字符+ *"全都作空串，是可以匹配s的。即dp[0] [j] = true(j = 2; j <= n; j += 2)。
   
   ③p为空串，s不为空串(第一列除去[0, 0])，这个时候不可能匹配，第一列除开[0] [0]其它都初始化为false。

4. 填表顺序
   填表不明白参考第一题，填表顺序为行从上到下，每一行从左到右。

5. 返回值
   依据状态表示，返回值为dp[m] [n]（m，n分别为s、p长度）。

• 代码实现

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        //处理下标映射
        s = " " + s,  p = " " + p;
        //dp[i][j]：p的[0,j]区域能否和s的[0,i]区域匹配
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = 1;  //空串可以匹配空串
        for(int j = 2; j <= n; j += 2)  //s为空串时p为连续的"字符 + *"是可以匹配的
        {
            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 if(s[i] == p[j] || p[j] == '.')
                {
                    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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

5.交错字符串（中等）

链接：交错字符串

• 题目描述
  

• 做题步骤

1. 状态表示
   有前面的做题经验，我们定义一个二维表，定义状态表示为dp[i] [j]：s1的[0, i]区间和s2的[0, j]区间能否交错组成s3的[0, i + j]区间。

2. 状态转移方程
   对s1的[0，i]区间和s2的[0，j]区间能否交错组成s3的[0, i + j]区间，我们分情况讨论：
   (1)s1[i] == s3[i + j]。这个时候只要s1的[0, i - 1]区间和s2的[0, j]区间可以组成s3的[0,i + j - 1]区间即真，即dp[i] [j] = (s1[i] == s3[i + j] && dp[i - 1] [j])
   
   (2)s2[j] == s3[i + j]。这个时候只要s1的[0, i]区间和s2的[0, j - 1]区间可以组成s3的[0,i + j - 1]区间即真，即dp[i] [j] = (s2[j] == s3[i + j] && dp[i] [j - 1])
   
   以上情况只要一个为真dp[i] [j]就为真。

3. 初始化
   为了避免越界以及方便初始化，我们引入空串的概念，多开一行一列。
   ①其中s1和s2都为空串可以组成空串s3，即dp[0][0] = true。
   
   ②当s1为空串，s2不为空串(第一列除去[0, 0])的时候可以由s2单独组成s3，前提是相等。即dp[0] [j] = true([1, j]区间s2与s3相等)。
   
   ③当s2为空串，s1不为空串(第一行除去[0, 0])的时候可以由s1单独组成s3，前提是相等。即dp[i] [0] = true([1, i]区间s1与s3相等)。

4. 填表顺序
   填表不明白参考第一题，填表顺序为行从上到下，每一行从左到右。

5. 返回值
   依据状态表示，返回值为dp[m] [n]（m，n分别为s1、s2长度）。

• 代码实现

class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        int m = s1.size(), n = s2.size();
        if(m + n != s3.size()) return false;  //两者相加比s3长度小，一定没办法组成的
        s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;  //处理下标映射
        //dp[i][j]：s1的[1,i]区间和s2的[1,j]区间能否交错组成s3的[1,i+j]区间
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for(int j = 1; j <= n; j++) // 初始化第⼀⾏，即s1为空，s2单独组成s3
        {
            if(s2[j] == s3[j]) dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++) // 初始化第⼀列,即s2为空，s1单独组成s3
        {
            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
26
27
28
29

6.两个字符串的最小ASCII删除和（中等）

链接：两个字符串的最小ASCII删除和

• 题目描述
  

• 做题步骤

1. 状态表示
   有前面的做题经验，我们定义一个二维表，定义状态表示为dp[i] [j]：s1的[0, i]区间和s2的[0, j]区间要达到相同的最小删除消耗。

2. 状态转移方程
   对s1的[0，i]区间和s2的[0，j]区间如何相同，我们分情况讨论：
   (1)s1[i] == s2[j]时，只需要让s1的[1, i - 1]和s2[1, j - 1]相同，即dp[i] [j] = dp[i - 1] [j - 1]。
   
   (2)s1[i] != s2[j]时，有两种选择：
   ①让s1的[1, i - 1]和s2的[1, j]相同，把多余的s1[i]删除，即dp[i] [j] = dp[i - 1] [j] + s1[i]。
   ②s1的[1, i]和s2的[1, j -1]相同，把多余的s2[j]删除，即dp[i] [j] = dp[i] [j - 1] + s2[j]。
   取①②情况的最小值即可，即(2)情况dp[i][j] = min(dp[i] [j - 1] + s2[j], dp[i - 1] [j] + s1[i])。
   
   这里提一下(1)情况的消耗是一定小于等于(2)的消耗，比如我一个短串和一个长串达到相等的消耗了x。现在我在短串后面加一些字符，想达到相等的话消耗一定会大于等于x。

3. 初始化
   为了避免越界以及方便初始化，我们引入空串的概念，多开一行一列。
   ①当s1和s2都为空串，消耗为0，即dp[0] [0] = 0。
   
   ②当s1为空串，s2不为空串(第一列除去[0, 0])的时候s2必须全部删除一直到为空串。即dp[0] [j] = dp[0] [j - 1] + s2[j] (j = 1; j <= n; j++)。
   
   ③当s2为空串，s1不为空串(第一行除去[0, 0])的时候s1必须全部删除一直到为空串。即dp[i] [0] = dp[i - 1] [0] + s1[i] (i = 1; i <= m; i++)。
   

4. 填表顺序
   填表不明白参考第一题，填表顺序为行从上到下，每一行从左到右。

5. 返回值
   依据状态表示，返回值为dp[m] [n]（m，n分别为s1、s2长度）。

• 代码实现

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        s1 = " " + s1, s2 = " " + s2;   //处理下标映射
        //dp[i][j]:s1的[1,i]区间和s2的[1,j]区间要达到相同的最小删除消耗
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        //s1为空串,s2要删除为空串的最小消耗
        for(int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j - 1] + s2[j];
        //s2为空串，s1要删除到空串的最小消耗
        for(int i = 1; i <= m; i++)
            dp[i][0] = dp[i - 1][0] + s1[i];

        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];
                else
                    dp[i][j] = min(dp[i][j - 1] + s2[j], dp[i - 1][j] + s1[i]);
            }
        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

7.最长重复子数组（中等）

链接：最长重复子数组

• 题目描述
  

• 做题步骤

1. 状态表示
   这个题不难，但是注意它是子数组而不是子序列，我们用前面的方式定义状态表示是会出错的，比如我定义状态表示为dp[i] [j]：n1的[0, i]区间与n2的[0, j]区间中的公共最长子数组长度。
   拿n1 = [3, 1, 1]和n2 = [1, 0, 1]举例，n1的[3, 1]区间和n2的[1, 0]区间公共最长子数组长度为1，当n1[2] == n2[2]的时候，公共最长子数组是没办法算的，你想dp[i - 1][j - 1] + 1是绝对不行的，因为n1[2]和n2[2]不一定能接在这个最长子数组后面，子数组必须是连续的！！！
   
   前面以区间为关注对象，没办法推导状态转移方程，那我们就以n1[i]和n2[j]为子数组结尾进行分析。
   我们定义一个二维表，定义状态表示为dp[i] [j]：同时以n1的i位置和n2的j位置结尾的公共最长子数组长度。

2. 状态转移方程
   对n1[i]和n2[j]，我们分情况讨论：
   (1)n1[i] == n2[j]时，可以同时接在以n1[i - 1]和n2[j - 1]为结尾的公共最长子数组后面，长度加1，即dp[i] [j] = dp[i - 1] [j - 1] + 1。
   
   (2)n1[i] != n2[j]时，同时以n1[i]和n2[j]为结尾的公共最长子数组不存在，即dp[i] [j] = 0。

3. 初始化
   为了避免越界，我们多开一行一列，dp数组下标从1开始，多出来的一行一列初始化为0即可。（注意处理与n1和n2数组的下标映射，因为n1和n2数组是从下标0开始的）

4. 填表顺序
   填表顺序为行从上到下，每一行从左到右。

5. 返回值
   没法直接确定最长子数组的结尾，所以一边dp一边更新最大值。

• 代码实现

class Solution {
public:
    int findLength(vector<int>& n1, vector<int>& n2) {
        int m = n1.size(), n = n2.size();
        //dp[i][j]表示以nums1的i位置和nums2的j位置结尾的公共最长子数组长度
        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(n1[i - 1] == n2[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