当前位置:   article > 正文

【动态规划】回文子串专题_动态规划 回文子串

动态规划 回文子串

1. 【LeetCode】647. 回文子串

题目链接

1.1 思路讲解

1.1.1 方法选择

这道题我们采用动态规划的解法,倒不是动态规划的解法对于这道题有多好,它并不是最优解。但是,这道题的动态规划思想是非常有用的,我们使用这道题的动态规划思想,可以让一些hard题变为easy题。

也就是说,这道题的动态规划思想其实就是起到了一个抛砖引玉的作用。

1.1.2 dp表的创建

如何表示出所有的子串的情况?可以用 i 表示某个子串的起始位置,用 j 来表示某个子串的末尾位置,暴力枚举,可以在N^2的时间复杂度内求出所有子串是否为回文子串。

所以,我们用二维dp[i][j]表来表示,以 i 位置为起始位置且以 j 位置为结尾的子串是否为回文子串。如果为回文子串那么dp[i][j]为true,否则为false。(我们人为规定 i <= j)

1.1.3 状态转移方程

我们要知道dp[i][j]为是否为回文子串,首先要判断 s[i] 是否等于 s[j]。

如果 s[i] != s[j],那么不管 i 和 j 中间的元素序列是怎样的,以 i 位置为起始位置,以 j 位置为终止位置的子串一定不为回文子串

如果 s[i] == s[j],那么需要对 i 和 j 的位置进行判断。

  1. 如果 i == j,那么说明当前初识位置和末尾位置在同一个位置,也就是说,子串只有一个元素,此时根据题意它为回文子串
  2. 如果 i + 1 == j,那么 i 和 j 的位置是相邻的,此时它们中间没有元素,它们位置上的元素又相同,那么一定是回文子串
  3. 如果 i + 1 < j,说明 i 位置 和 j 位置中间还有其他元素,此时只需判断dp[i+1][j-1]为true还是false即可

1.1.4 填表顺序

由于我们求dp[i][j]的时候,需要用到 dp[i+1][j-1],且 i 的循环为外层的循环,所以让 i 从大到小循环即可。

1.2 整体代码

在这里插入图片描述

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        // 创建二维dp表,dp表中每个位置的初始值为false
        vector<vector<bool>> dp(n, vector<bool>(n));
        
        int ret = 0; // 用于保存有多少位true的dp位置,即有多少个回文子串
        // 在循环时 i 从大到小进行循环
        for (int i = n - 1; i >= 0; --i)
        {
            // j的循环顺序其实无所谓,只要循环的区间在[i, n)即可
            for (int j = i; j < n; ++j)
            {
                // 根据状态转移方程求dp[i][j]
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                // 如果dp[i][j]为true,增加ret
                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

2. 【LeetCode】5. 最长回文串

题目链接

2.1 思路讲解

与求回文子串思路差别不大

它也就是求出每一个回文子串后,不是统计有多少个回文子串,而是挑出最长的那个回文子串并在循环结束之后返回即可。

代码也只不过改动了一点点而已。

2.2 代码实现

在这里插入图片描述

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int start = 0; // 最长的回文子串的起始位置
        int len = 0; // 最长的回文子串的长度
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                // 如果该位置为回文子串,那么判断长度是否大于之前最长的长度
                // 如果大于,则对起始位置和最长长度进行更新
                if (dp[i][j] == true && j - i + 1 > len)
                {
                    len = j - i + 1;
                    start = i;
                }
            }
        }
        // 根据起始位置和长度返回最长回文子串
        return s.substr(start, len);
    }
};
  • 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

3.【LeetCode】094. 分割回文串II

3.1 解题思路

3.1.1 创建dp表

这道题我们使用动态规划的方法来解,首先创建一个大小为字符串长度的dp表。dp[i] 表示 s[0, i] 的字符串最小划分多少次可以全划分为回文串。

3.1.2 状态转移方程

求状态转移方程,我们要考虑两种情况。s[0, i] 的字符串是回文串和不是回文串的情况。

注意,这里假设我们已经知道了哪段字符串是不是回文串,至于是如何知道的后面会说。

  • 如果s[0, i]是回文串,那么问题很简单,不用切割就行,即dp[i] = 0;
  • 如果s[0, i]不是回文串,我们要新增一个变量 j ,j 的范围为 (0, i],这里说明一些j的边界情况,j 要大于0的原因是 j 为0的情况即不用分割s[0, i]的情况(即s[0, i]为回文串的情况),j 为 i 的情况即 s[0, i-1] 中找不到从0开始且为回文串的情况。用这个 j 变量,我们遍历 j 的情况,j 是小于等于 i 的,那么 dp[j-1] 的值我们是知道的。如果从 j 到 i 的字符串是回文串,那么我们就令 dp[i] = min(dp[i], dp[j - 1] + 1); 遍历所有 j 的情况,就能求出 dp[i] 的最小值了。

在这里插入图片描述

3.1.3 提前求出所有子串是否是回文串

这个通过上面的题解也就能知道了。

3.2 整体代码

在这里插入图片描述

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        // 求出所有子串是否为回文串
        vector<vector<bool>> isPal(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i)
            for (int j = i; j < n; ++j)
                if (s[i] == s[j]) 
                    isPal[i][j] = i + 1 < j ? isPal[i+1][j-1] : true;
        
        // 创建dp表,由于是求最小值,可以先将所有位置初始化为最大
        vector<int> dp(n, INT_MAX);  
        for (int i = 0; i < n; ++i)
        {
            if (isPal[0][i]) dp[i] = 0;
            else
            {
                for (int j = 1; j <= i; ++j)
                    if (isPal[j][i]) dp[i] = min(dp[i], dp[j-1] + 1);
            }
        }
        return dp[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

4.【LeetCode】516. 最长回文子序列

4.1 思路讲解

4.1.1 创建dp表

此题采用动态规划的方法,创建一个二维dp表,dp[i][j]表示s[i, j]中最大回文子序列的长度。且我们人为规定 i 是一定小于等于 j 的。

4.1.2 状态转移方程

在求dp[i][j]时,首先要判断s[i]和s[j]是否相同。

如果 s[i] == s[j]

  1. 如果 i == j,说明 i 与 j 的位置相同,此时dp[i][j] 就为 1
  2. 如果 i + 1 == j,说明 i 与 j 相邻,此时dp[i][j] 就为2
  3. 其他情况下,说明 i 和 j 中间有其他元素,那么此时dp[i][j] = dp[i+1][j-1] + 2;

如果s[i] != s[j]

那么此时,说明不能同时以 i 为开头和以 j 为结尾,我们去掉这种情况寻找一个最大子序列即可。方法就是在 dp[i+1, j] 和 dp[i, j-1] 中选一个最大的即可。即dp[i][j] = max(dp[i+1[j], dp[i][j-1]);

4.1.3 不需考虑边界问题

在求dp[i][j]的时候,我们可能会用到 i + 1 和 j - 1,在它们有可能越界的时候,一定是 i 等于 j 的时候。我们创建的dp表是二维的,我们可以想到,在可能越界的时候,就是左上角的位置或者右下角的位置,但其实这两个位置满足 i == j,那么dp[i][j] 就会被直接赋值为1,此时就不会用到 i + 1 和 j - 1 了,所以其实我们不用考虑越界的情况。

4.2 整体代码

在这里插入图片描述

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        // 创建二维dp表,dp[i][j]表示s[i, j]最大子序列的长度
        vector<vector<int>> dp(n, vector<int>(n));
        // dp[i][j]需要用到dp[i+1][j-1]
        // 所以i从大到小循环,j从小到大循环,且i是小于等于j的
        for (int j = 0; j < n; ++j)
        {
            for (int i = j; i >= 0; --i)
            {
                if (s[i] == s[j])
                {
                    if (i == j) dp[i][j] = 1;
                    else if (i + 1 == j) dp[i][j] = 2;
                    else 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
  • 22
  • 23
  • 24

5. 【LeetCode】1312. 让字符串成为回文串的最少插入次数

题目链接

5.1 思路讲解

5.1.1 创建dp表

采用动态规划的解法,可以借鉴以上题的思路。创建二维dp表,dp[i][j]表示 i 到 j 位置变成回文串的最小操作次数。(我们人为规定 i 是小于等于 j 的)

5.1.2 状态转移方程

同样我们要分 s[i] == s[j] 和 s[i] != s[j] 的情况讨论。

如果 s[i] == s[j]

  1. 如果 i == j,那么此时 i 与 j 的位置相同,一个字符本身就是回文串,dp[i][j] = 0
  2. 如果 i + 1 == j,那么此时 i 与 j 位置相同,此时这两个字符同样也是回文串,dp[i][j] = 0
  3. 如果 i + 1 < j ,那么此时 i 与 j 中间有其他字符,dp[i+1][j-1]为 i 和 j 中间字符串要变为回文串的最小操作次数,因为 s[i] == s[j],所以此时加上 i 和 j 位置的字符之后, dp[i][j] = dp[i+1][j-1]。

如果 s[i] != s[j]

i 和 j 位置的字符不相同,那么此时只需找到 dp[i+1][j] 和 dp[i][j-1] 的最小值,然后将最小的那个加1即可,即dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1; 就相当于再在另一端补上一个与 s[i] 或者 s[j] 相同的字符即可。

在这里插入图片描述

5.1.3 不需考虑边界问题

这道题和第四题一样,都是需要考虑越界的,具体原因和第四题相同。

在求dp[i][j]的时候,我们可能会用到 i + 1 和 j - 1,在它们有可能越界的时候,一定是 i 等于 j 的时候。我们创建的dp表是二维的,我们可以想到,在可能越界的时候,就是左上角的位置或者右下角的位置,但其实这两个位置满足 i == j,那么dp[i][j] 就会被直接赋值为0,此时就不会用到 i + 1 和 j - 1 了,所以其实我们不用考虑越界的情况。

5.2 整体代码

在这里插入图片描述

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        // dp[i][j]表示s[i, j]变成回文串的最小操作次数
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        // dp[i][j] 需要用到 dp[i+1][j-1]
        // 所以i应该从大到小遍历,j应该从小到大遍历
        // 且i是要小于等于j的,所以i的初始值为j
        // 因为i的初始值为j,所以j在循环外层,i在内层
        for (int j = 0; j < n; ++j)
        {
            for (int i = j; i >= 0; --i)
            {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : 0;
                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
  • 23
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/660197
推荐阅读
相关标签
  

闽ICP备14008679号