动态规划之回文串问题_回文子串 动态规划

1. 回文子串

1.题目链接：回文子串
2.题目描述：
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

3.问题分析：动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。 所以这道题还是寻找相同子问题，然后求解。对于在字符串中寻找回文子串，在字符串中可以先确定一个字符(字符串)，然后在这个字符(字符串)的两侧扩展字符，如果扩展前的字符(字符串)是一个回文串，并且扩展的左右两侧的字符是相同的，那么扩展后的字符串就是一个回文串。这道题所求的是回文子串的数目，所以需要将这个字符串中的所以子串都枚举出来，寻找符合条件的数目。所以可以用一个二维dp表来表示以 i 为起始，以 j 为结尾的字符串是不是回文串，如果是回文串，那么就给返回值的结果加1。

1. 状态表示：如上述分析用一个二维布尔类型的dp表来表示以 i 为起始，以 j 为结尾的字符串是不是回文串。
2. 状态转移方程：用两个for循环遍历s字符串，寻找子回文串，要判断以 i 为起始，以 j 为结尾的字符串是不是回文串，如上述所分析，对于中间元素来说，左右两边的元素都相同那么该字符串就为回文串；首先 i 位置的元素要等于 j 位置的元素，然后再判断以 i + 1为起始，以 j - 1为结尾的字符串是不是回文串，这样一个问题就被拆分成子问题。状态转移方程为：dp[i][j] = dp[i + 1][j - 1]；还需要注意对临界情况分析，因为到最后的子问题可能会有多种情况：s可能为某一个字符串中的子串，i，j 为指向s起始和结尾的下标，假设1，s的长度为1个，i + 1,j - 1当作越界，但s是一个回文串；假设2，s的长度为2，并且 s[i] = s[j]，i + 1,j - 1也越界，s也是一个回文串；假设3，s的长度为3，并且 s[i] = s[j]，i+1,j-1后刚好接到假设1；假设4，s的长度为4，i+1,j-1后接到假设2，所以需要对长度为1和2的子串进行判断。 即当子串的长度为1或2时，若s[i]=s[j]，则dp[i][j] = true。
3. 初始化：dp表中全初始化为false。
4. 填表顺序：由状态转移方程dp[i][j] = dp[i + 1][j - 1]可知，要求 i，j 位置需要知道 i + 1，j - 1位置的dp，所以需要从下往上，从做往右初始化。
5. 返回值：返回dp表中所有为true的个数。

4.代码如下：

class Solution{
public:
    int countSubstrings(string s) {
        int n = s.size();
        int ret = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));

        for (int i = n - 1; i >= 0; --i) //i从下往上填写
        {
            for (int j = i; j < n; ++j) //j从左往右填写
            {
                if (s[i] == s[j])
                {
                    if (j - i < 2)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                //或者如下代码
                //if (s[i] == s[j])
                //    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j])
                    ++ret;
            }
        }
        return ret;
    }
};
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

2. 最长回文子串

1.题目链接：最长回文子串
2.题目描述：
给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

3.题目分析：这道题也是寻找所有的回文子串，但求的是回文子串的最长长度，所以当遇到一个回文子串时，需要计算回文子串的长度，然后保留最长的长度；在这里保存子字符串需要子字符串的起始，结尾位置，还需要保存子字符串的长度，再细分一下，只需要子字符串的起始位置和长度即可；在string类型中，有一个函数substr，string substr (size_t pos = 0, size_t len = npos) const;返回类型为string，所以只要知道最长子字符串的起始位置和长度即可。

1. 状态表示：用一个二维布尔类型的dp表来表示以 i 为起始，以 j 为结尾的字符串是不是回文串。
2. 状态转移方程：dp[i][j] = dp[i + 1][j - 1].
3. 初始化：dp表中全初始化为false。
4. 填表顺序：由状态转移方程dp[i][j] = dp[i + 1][j - 1]可知，要求 i，j 位置需要知道 i + 1，j - 1位置的dp，所以需要从下往上，从做往右初始化。
5. 返回值：返回s中的最长子字符串。

4.代码如下：

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int begin = 0, length = 0; //记录最长子字符串的起始位置和长度
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = j - i < 2 ? true : dp[i + 1][j - 1];
                    if (dp[i][j]) //保留最长的回文子串
                    {
                        int l = j - i + 1;
                        if (l > length)
                        {
                            length = l;
                            begin = i;
                        }
                    }
                }
            }
        }
        return s.substr(begin, length);
    }
};
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

3. 分割回文串 IV

1.题目链接：分割回文串 IV
2.题目描述：
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = “abcbdd”
输出：true
解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。

示例 2：

输入：s = “bcbddxy”
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

3 <= s.length <= 2000
s​​​​​​ 只包含小写英文字母。

3.题目分析：这道题首先也是寻找s字符串中的回文子串，然后再在回文子串中寻找3个可以拼接s字符串的回文子串，具体如何寻找？寻找3个子串，i，j 位置表示的是由 i 到 j 为回文子串，那么i位置之前和j 位置之后都是回文子串，那么就可以返回true，这三个位置用dp[0][i - 1]，dp[i][j]，dp[j + 1][n - 1]表示，即这三个位置的bool值都为true，那么返回 true ，否则返回 false ；如果分割为四个子串该如何解决？五个子串呢？六个以及k个子串呢？这个思路用的应该是深度优先遍历，将每层为true的路径保存起来，(比如s的下标从0到2,4,6是回文串，1到…) 然后挨个遍历，寻找符合题意的路径即可，路径问题还没有深入学习，所以就先不写具体代码了。

4.代码如下：

class Solution
{
public:
    bool checkPartitioning(string s) 
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));

        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j])
                    dp[i][j] = j - i < 2 ? true : dp[i + 1][j - 1];
            }
        }
        for (int i = 1; i < n - 1; ++i)
        {
            for (int j = i; j < n - 1; ++j)
            {
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
                    return true;
            }
        }
        return 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

4. 分割回文串 II

1.题目描述：分割回文串 II
2.题目描述：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

示例 2：

输入：s = “a”
输出：0

示例 3：

输入：s = “ab”
输出：1

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

3.题目分析：如上述几道题一样，先确定所有的回文子串，然后再回文子串中寻找最少能拼接s字符串的个数。在寻找最少能拼接s字符串的个数时，又是一个dp问题，如要寻找一个字符串中最小的分割次数，可以转为求字符串中某一个子串的最小的分割次数；所以定义一个f[i]：表示s 中[0, i] 区间上的字符串，最少分割的次数。然后一步一步分析：如果0~i位置是回文串，则f[i] = 0；如果不是，那么就在0到i中寻找回文子串，定义一个位置j，j到i如果是回文子串，那么0到i最小的分割次数就等于j - 1位置最小的分割次数加1，即f[i] = f[j - 1] + 1。 最后返回f表中最后一个位置的元素。

1. 状态表示：dp[j] 表示： s 中[0, i]区间上的字符串，最少分割的次数。
2. 状态转移方程：f[i] = min(f[i], f[j - 1] + 1)。
3. 初始化：f表全初始化为最大值即可。
4. 填表顺序：从左往右。
5. 返回值：返回f表中最后一个位置的元素。

4.代码如下：

class Solution
{
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j])
                    dp[i][j] = j - i < 2 ? true : dp[i + 1][j - 1];
            }
        }
        vector<int> f(n, INT_MAX);
        for (int i = 0; i < n; ++i)
        {
            if (dp[0][i]) //如果0~i是回文串，则不需要拆分
                f[i] = 0;
            else
            {
                //否则在j~i中寻找最小的分割次数
                for (int j = 0; j < i + 1; ++j)
                {
                    if (dp[j][i])
                        f[i] = min(f[i], f[j - 1] + 1);
                }
            }
        }
        return f[n - 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
28
29
30
31
32
33

5. 最长回文子序列

1.题目链接：最长回文子序列
2.题目描述：
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

3.题目分析：这道题需要找到字符串中回文子序列，子序列不一定连续，遍历字符串肯定需要从某个位置到某个位置，所以定义dp[i][j]表示：s字符串 [i, j] 区间内的所有的⼦序列中，最⻓的回⽂⼦序列的⻓度；然后在i，j 位置进行分析，如果i = j，此时s[i] = s[j]，则回文子序列长度为1，即dp[i][j] = 1。如果 i 不等于 j ，并且s[i] = s[j]，那么i，j 位置的值是不是比i + 1,j - 1位置的长度多2，即dp[i][j] = dp[i + 1][j - 1] + 2；如果s[i] 不等于s[j]，那么就在dp[i][j - 1]，dp[i + 1][j]中找最大的值保留即可，为什么在dp[i][j - 1]，dp[i + 1][j]中寻找?因为i,j不是回文串，(i,j-1)，(i+1,j)中可能是回文串也可能不是，但是这两个位置存放的是最⻓的回⽂⼦序列的⻓度。因为是从下到上遍历，所以最后返回dp[0][n - 1]的值。

1. 状态表示：dp[i][j]表示：s字符串 [i, j] 区间内的所有的⼦序列中，最⻓的回⽂⼦序列的⻓度。
2. 状态转移方程：当 s[i] == s[j] 时： dp[i][j] = dp[i + 1][j - 1] + 2 ； 当s[i] != s[j] 时： dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])。
3. 初始化：dp表全初始化为0，当 i = j 时，dp[i][j] = 1。
4. 填表顺序：从下到上，从左往右。
5. 返回值：返回dp[0][n - 1]的值。

4.代码如下：

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

6. 让字符串成为回⽂串的最⼩插⼊次数

1.题目链接：让字符串成为回⽂串的最⼩插⼊次数
2.题目描述：
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：

输入：s = “zzazz”
输出：0
解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = “mbadm”
输出：2
解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。

示例 3：

输入：s = “leetcode”
输出：5
解释：插入 5 个字符后字符串变为 “leetcodocteel” 。

提示：

1 <= s.length <= 500
s 中所有字符都是小写字母。

3.问题分析：这道题也是从 i 位置到 j 位置进行分析，先定义一个dp[i][j]表示：字符串 [i, j] 区域成为回⽂⼦串的最少插⼊次数。然后对i，j 位置进行分析，如果s[i] = s[j]，那么 [i, j] 区间内成为回⽂⼦串的最少插⼊次数，取决于 [i + 1, j - 1] 区间内成为回⽂⼦串的最少插⼊次数； 若 i = j 或 i = j - 1 ，那么 [i, j] 区间⼀定是回⽂⼦串，成为回⽂⼦串的最少插⼊次数是0。此时 dp[i][j] = i >= j - 1 ? 0 : dp[i + 1][j - 1] 。如果s[i] != s[j]，那么就如上道题一样，在区间(i,j-1)，(i+1,j)中寻找插入次数最小的，此时dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1；由状态转移方程可知，要求dp[i][j]，先要知道dp[i+1][j] 和dp[i][j-1]的值，所以对于i来说，应该从下到上遍历，对于j来说，应该从左往右遍历；因为是从下到上遍历，所以最后返回dp[0][n - 1]的值。

1. 状态表示：dp[i][j]表示：字符串 [i, j] 区域成为回⽂⼦串的最少插⼊次数。
2. 状态转移方程：如果 s[i] == s[j] ： dp[i][j] = i >= j - 1 ? 1 : dp[i + 1][j - 1] ；如果 s[i] != s[j] ： dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1 。
3. 初始化：dp表全初始化为0。
4. 填表顺序：从下到上，从左往右。
5. 返回值：返回dp[0][n - 1]的值。

4.代码如下：

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = j - i < 2 ? 0 : dp[i + 1][j - 1];
                }
                else
                {
                    dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22