LycTechStack

Lyc的个人成长技术栈

0%

【动态规划】（三）线性动态规划之双串问题

发表于 更新于 分类于
本文字数： 10k 阅读时长 ≈ 9 分钟

双串问题

线性动态规划的另一大类问题就是双串问题，双串问题有两个输入串，长度分别为 m, n，此时子问题需要用 i, j 两个变量表示，分别代表第一个串和第二个串考虑的位置， $dp[i][j]$ 表示第一串考虑 [0..i] ，第二串考虑 [0..j] 时原问题的解。双串问题相比于单串问题难度更大，虽然状态的定义大同小异，但是状态转移需要考虑的情况往往更加复杂。

双串问题同样分为两种情况，大多数情况下较大规模的子问题只与常数个较小规模的子问题有关，其中较小规模可能是 i 更小，或者是 j 更小，也可以是 i，j 同时变小。此时状态转移代码常见的形式是：

1
2
3
for i = 1..m
    for j = 1..n
        dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

另一种情况类似单串中依赖比 i 小的 O(n) 个子问题的情况，复杂度相对更高。

1 经典问题：LCS系列

最长公共子序列

问题描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

这是最经典的双串动态规划问题，也比较简单，定义状态 $dp[i][j]$ 表示在 text1 的 [0…i] 上和 text2 的 [0…j] 上最长公共子序列长度，于是状态转移分为两种情况：

  • 当前字符 text1[i] == text2[j]，那么此时找到了公共字符，$dp[i][j]$ 就等于 $dp[i-1][j-1]$ 的基础上加 1
  • 当前字符 text1[i] != text2[j]，那么此时二者不是公共字符，$dp[i][j]$ 取决于 $dp[i-1][j]$ 和 $dp[i][j-1]$ 中的较大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(text1[i-1] == text2[j-1]) 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];
    }
};
两个字符串的最小ASCII删除和

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

可以转换成最长公共子序列问题，只不过这次我们求最长公共子序列的 ASCII 值的和，然后用两个字符串的总ASCII 值的和减去两倍的最长公共子序列的 ASCII 值的和，剩下的就是删掉的 ASCII 值的最小和。

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

当然本题也可以直接定义和原问题一致的动态规划状态，具体可以看官方题解的方法。

最长重复子数组

和最长公共子序列的区别在于重复子数组必须是连续的，因此当前两个数不相等时，不能再继续传递 $dp[i-1][j]$ 和 $dp[i][j-1]$ 中的较大值，而是要将 $dp[i][j]$ 置 0 ，阻断状态传递，最终的结果取所有状态中的最大值就是最长重复子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    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, 0));
        int ans = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = nums1[i-1] == nums2[j-1] ? dp[i-1][j-1] + 1 : 0;
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

动态规划是本题最容易想到并实现的方法，但并不是最好的方法，本题使用滑动窗口会效率会更高，不过不容易想到且编码相对复杂一些，具体可以看滑动窗口解法。

2 经典问题：字符串匹配系列

编辑距离

问题描述：
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对任何一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

编辑距离是非常经典的一个问题，并且在机器翻译、语音识别等领域也应用广泛，值得深入研究。

题目实际上的意思是可以对两个单词都进行操作，只要最终两个单词相同即可，但我们要保证总操作次数最少，即编辑距离最小。

我们首先考虑状态的定义，双串问题的状态定义之前已经说过，几乎都是一样的，因此我们定义 $dp[i][j]$ 表示从 word1[0…i] 转换成word2[0…j] 所需要的最小操作数，也就是 word1[0…i] 到 word2[0…j] 的最小编辑距离。从前向后遍历两个单词更新状态，最终 $dp[m][n]$ 就是答案。接下来考虑状态转移过程。

因为我们对两个单词都可以插入、删除和替换，所以一共可以进行六种操作，看起来非常复杂，但我们仔细分析一下，假设某一时刻的状态 word1[0…i] 表示成 A ，word2[0…j] 表示成 B，那么从 A 转换到 B 有以下几种情况：

  • 在 A 的末尾插入一个字母，或者在B的末尾删除一个字母。这两种操作是等价的，比如 A=goo， B=good，此时从 A 转换到 B 我们可以在 A 的末尾插入字母 d ，也可以把 B 末尾的 d 删掉，因此这两种操作等价；
  • 在 B 的末尾插入一个字母，或者在A的末尾删除一个字母。这两种操作是等价的，理由同上；
  • 在 A 中替换一个字母或者在 B 中替换一个字母。这两种操作是等价的，比如 A=good， B=goom，我们可以把 A 的末尾 d 替换为 m，也可以把 B 的末尾 m 替换为 d。

因此所有的六种操作实际上只有三种操作，这里要说明一下为什么都在末尾操作，因为我们的状态定义 $dp[i][j]$ 表示的就是以当前字母 word1[i] 结尾的单词和 word2[j] 结尾的单词之间的最小编辑距离，此前的编辑距离都已经计算完毕并且保证最小，因此我们每次只要关注单词末尾的操作就可以了。并且这里所有操作的顺序都不会影响最终结果，无论是先插入后删除，还是先删除后插入都不影响最终结果，所以我们在末尾的操作也与顺序无关，只要关注最小操作次数即可。

有了以上的分析，再去进行状态转移就很简单了，因为每次我们只需要考虑三种操作的情况：

  • 在 A 的末尾插入一个字母（相当于在 B 的末尾删除一个字母）。假如我们已经知道了从 horse 到 ho 的最小编辑距离为 d，那么从 horse 到 hos 的最小编辑距离就是 d 加上1，因为我们可以在d次操作后将 horse 变为 ho ，此时要么在末尾加上一个字母 s ，要么把 hos 中的 s 删掉，二者就相同了，因此这种情况下状态转移方程为：

    1
    dp[i][j] = dp[i][j-1] + 1

  • 在 B 的末尾插入一个字母（相当于在 A 的末尾删除一个字母）。和上面的情况类似，因此状态转移方程为：

    1
    dp[i][j] = dp[i-1][j] + 1

  • 在 A 末尾替换一个字母（相当于在 B 末尾替换一个字母）。此时又分为两种情况：

    • A末尾的字母和B末尾的字母相等，此时不需要任何操作，状态转移方程为：

      1
      dp[i][j] = dp[i-1][j-1]

    • A末尾的字母和B末尾的字母不相等，此时可以任意替换一次使二者相等，也就是操作一次：

      1
      dp[i][j] = dp[i-1][j-1] + 1

这就是状态转移时全部可能的情况，取他们之中的最小值，就可以保证每次状态转移时都是二者之间的最小编辑距离。

最后讨论一下边界情况：

  • 当 i = 0 时，word1[0…i] 为空，此时想要转化为 word2[0…j] 需要操作 j 次，要么在 word1 末尾插入 j 次， 要么在 word2 末尾删除 j 次
  • 同理当 j = 0 时，word2[0…j] 为空，此时想要转化为 word1[0…i] 需要操作 i 次
  • i 和 j 都为 0 时，编辑距离显然为0

这样一来代码就很好写了：

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        // 有一个字符串为空串
        if (n * m == 0) return n + m;
        // 边界状态初始化
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= m; j++) {
            dp[0][j] = j;
        }
        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int insert_a = dp[i][j - 1] + 1;    //在A末尾插入的情况
                int insert_b = dp[i - 1][j] + 1;    //在B末尾插入的情况
                int replace = dp[i - 1][j - 1];        //替换的情况
                if (word1[i - 1] != word2[j - 1]) replace += 1;
                dp[i][j] = min(insert_a, min(insert_b, replace));
            }
        }
        return dp[n][m];
    }
};

注意到 $dp[i][j]$ 的状态只与$dp[i][j-1]$ 、$dp[i-1][j]$ 和 $dp[i-1][j-1]$ 有关，因此可以不用二维数组保存状态，改为一维，每次更新时， $dp[i][j-1]$ 就是 $dp[j-1]$ 已经计算完毕，$dp[i-1][j]$ 就是当前正在计算的位置 $dp[j]$，同时也是下一次计算时的 $dp[i-1][j-1]$，因此再用一个额外变量记录 $dp[i-1][j-1]$ 即可。

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        if (n * m == 0) return n + m;
        vector<int> dp(m + 1);
        // 边界状态初始化
        for (int j = 0; j <= m; j++) {
            dp[j] = j;
        }
        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            int p = dp[0];  //保存dp[i-1][j-1]
            dp[0] = i;  //相当于之前的另一个初始化
            for (int j = 1; j < m + 1; j++) {
                int insert_a = dp[j - 1] + 1;   //dp[i][j-1] + 1
                int insert_b = dp[j] + 1;   //dp[i-1][j] + 1
                int replace = p;
                if (word1[i - 1] != word2[j - 1]) replace += 1;
                p = dp[j];  //更新dp[i-1][j-1]，上一次的dp[i-1][j]，就是下一次的dp[i-1][j-1]
                dp[j] = min(insert_a, min(insert_b, replace));
            }
        }
        return dp[m];
    }
};
通配符匹配

问题描述：

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

其中：'?' 可以匹配任何单个字符；'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

这是一个比较困难的问题，状态定义同样是 $dp[i][j]$，表示字符串 s 以 i 结尾的子串和字符模式 p 以 j 结尾的子串能否成功匹配。

s中只包含小写字母，p中包含小写字母、问号和星号，因此状态转移对应的就是三种情况：

  • s[i] 和 p[j] 都是字母：此时 dp[i][j] = dp[i-1][j-1] && s[i] == p[j]

  • p[j] 是问号：此时 s[i] 一定匹配，因此 dp[i][j] = dp[i-1][j-1]

  • p[j] 是星号：此时 s[i] 也一定匹配，但是要考虑是否消耗掉这个星号，因为一个星号可以匹配多个字母，如果消耗掉这个星号，则 dp[i][j] = dp[i-1][j]；如果不消耗这个星号，则 dp[i][j] = dp[i][j-1]，具体是否使用要看不用星号是否能够匹配，如果不用就可以匹配那就无需使用，如果不用就无法匹配了，那就必须使用，因此最终dp[i][j] = dp[i-1][j] || dp[i][j-1]

然后是边界条件：

  • $dp[0][0]$ 表示两个空串，可以匹配，所以 $dp[0][0]=true$
  • $dp[i][0]$ 表示模式串为空，那么字符串无论如何都无法匹配，因此 $dp[i][0] = false$
  • $dp[0][j]$ 表示字符串为空，那么只有模式串为星号才能匹配，因此模式串开头是星号的位置$dp[0][j]=true$，其他位置都为$false$

这样一来就问题就解决了。

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
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p[i - 1] == '*') {
                dp[0][i] = true;
            }
            else {
                break;
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
                else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

本题用贪心法也可以，并且不需要额外的空间，具体可以查看官方题解方法二，但还是以理解动态规划方法为主。

正则表达式匹配

问题描述：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

其中：'.' 可以匹配任何单个字符；'*' 可以匹配零个或多个前面的那一个元素。

这道题是通配符匹配的进阶版，因此我们可以完全按照通配符匹配的思路来分析这道题，再去解决特殊的情况。

状态定义同样是 $dp[i][j]$，表示字符串 s 以 i 结尾的子串和字符模式 p 以 j 结尾的子串能否成功匹配。

s中只包含小写字母，p中包含小写字母、点和星号，因此状态转移对应的就是三种情况：

  • s[i] 和 p[j] 都是字母：此时 dp[i][j] = dp[i-1][j-1] && s[i] == p[j]

  • p[j] 是点：此时 s[i] 一定匹配，因此 dp[i][j] = dp[i-1][j-1]

  • p[j] 是星号：这时情况要比通配符更复杂一些，因为星号代表的是零个或多个前面的那一个元素，因此我们要判断 s[i] 和 p[j-1] 是否匹配：

    • 如果匹配，那么我们把 p[j-1] 和 p[j] 看成一个整体，此时这两个字符组成的整体的作用和通配符匹配中星号的作用完全一样，只不过是一个占用两个位置的星号，因此我们可以选择消耗掉星号来匹配s[i] ，或者不消耗掉星号，继续往后匹配，此时状态转移方程和通配符匹配中一致，不过记得这次星号占两位：

      1
      dp[i][j] = dp[i-1][j] || dp[i][j-2]

    • 如果不匹配，同样把 p[j-1] 和 p[j] 看成一个整体相当于一个通配符中的星号，但是此时星号无作用，相当于匹配了一个空字符，直接丢掉即可，此时状态转移就是：

      1
      dp[i][j] = dp[i][j-2]

接下来是边界条件：

  • $dp[0][0]$ 表示两个空串，可以匹配，所以 $dp[0][0]=true$
  • $dp[i][0]$ 表示模式串为空，那么字符串无论如何都无法匹配，因此 $dp[i][0] = false$
  • $dp[0][j]$ 表示字符串为空，至于能否和模式串匹配，需要用上面的状态转移流程去判断，因此我们不需要专门去初始化，只要遍历字符串 s 时从 0 开始即可。

代码如下：

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
33
34
35
36
37
38
39
40
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1, 0));
        dp[0][0] = 1;
        //判断两个位置是否匹配
        auto matches = [&](int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };
        //动态规划推导
        for(int i = 0; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(matches(i, j))
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j-1] == '*')
                {
                    if(matches(i, j - 1))
                    {
                        dp[i][j] = dp[i-1][j] || dp[i][j-2];
                    }
                    else{
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

3 其他双串问题

交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味着字符串 a 和 b 连接。

定义状态 $dp[i][j]$ 表示字符串 s1 以 i 结尾的子串和字符串 s2 以 j 结尾的子串能否交错形成 s3 以 i+j-1 结尾的子串。

状态转移只有两种情况：

  • 如果 $s1[i] == s3[i+j-1]$，那么 $dp[i][j] = dp[i-1][j]$
  • 如果 $s2[j] == s3[i+j-1]$，那么 $dp[i][j] = dp[i][j-1]$

边界条件:

  • $dp[0][0]=true$
  • $dp[i][0]$ 和 $dp[0][j]$ 都相当于在和 s3 做字符串匹配，因此直接在循环中从 0 开始遍历两个字符串即可

由于 $dp[i][j]$ 只与 $dp[i-1][j]$ 和 $dp[i][j-1]$ 有关，因此只需使用一维数组。

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
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), k = s3.size();
        if(m + n != k) return false;
        vector<int> dp(n+1);
        dp[0] = 1;
        for(int i = 0; i <= m; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                int t = i + j - 1;
                if(i > 0)
                {
                    dp[j] &= (s1[i-1] == s3[t]);    //相当于dp[i][j] = dp[i-1][j] && s1[i-1] == s3[t]
                }
                if(j > 0)
                {
                    dp[j] |= (s2[j-1] == s3[t] && dp[j-1]);
                }
            }
        }
        return dp[n];
    }
};
不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

定义状态 $dp[i][j]$ 表示字符串 s 以 i 结尾的子串中，字符串 t 以 j 结尾的子串出现的次数。

考虑状态转移：

  • 如果 $s[i] \neq t[j]$，则 $dp[i][j] = dp[i-1][j]$
  • 如果 $s[i] = t[j]$，分为两种情况：
    • 使用 s[i] 和 t[j] 匹配，此时 $dp[i][j] = dp[i-1][j-1]$
    • 不使用 s[i] 和 t[j] 匹配，此时 $dp[i][j] = dp[i-1][j]$

边界条件：

  • $dp[0][0] = 1$，空串是任何串的子串
  • $dp[i][0] = 1$，理由同上
  • $dp[0][j] = 0$，空串中不包含任何一个非空子串

同时考虑到，如果 t 的长度大于 s 的长度，直接返回 0 即可，因此遍历 j 的时候也只需要遍历到比 i 小即可，因为 j 大于 i 时 $dp[i][j]$ 也一定为 0.

代码如下：

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
class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        if(m < n) return 0;
        //使用unsigned long long是为了通过一些阴间用例
        vector<vector<unsigned long long>> dp(m+1, vector<unsigned long long>(n+1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 0; j <= min(i, n); j++)
            {
                if(j == 0) dp[i][0] = 1;
                else if(s[i-1] != t[j-1])
                {
                    dp[i][j] = dp[i-1][j];
                }
                else if(s[i-1] == t[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; 
                }
            }
        }
        return dp[m][n];
    }
};
扰乱字符串

有余力可以了解。

---- 本文结束 知识又增加了亿点点！----

文章版权声明 1、博客名称：LycTechStack
2、博客网址：https://lz328.github.io/LycTechStack.github.io/
3、本博客的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系博主进行删除处理。
4、本博客所有文章版权归博主所有，如需转载请标明出处。
相关文章