动态规划回文子串-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划回文子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

647. 回文子串
双指针法：

遍历回文中心---->一个回文中心---->两个回文中心

class Solution {
public:
    int countSubstrings(string s) {
        int result=0;
        for(int i=0; i<s.size(); i++){
            result += count(s, i, i);
            result += count(s, i, i+1);
        }
        return result;
    }
    int count(string s, int i, int j){
        int cnt=0;
        while(i>=0 && j<s.size() && s[i]==s[j]){
            cnt++;
            i--;
            j++;
        }
        return cnt;
    }
};

遍历边界，找出回文中心，其实还是变相的找回文中心

class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        int n = s.size();
        for(int i=0; i<n*2+1; i++){
            int left = i/2;
            int right = i/2 + (i+1)%2;
            while(left>=0 && right<n && s[left]==s[right]){
                result++;
                left--;
                right++;
            }
        }
    return result;
    }
};

动态规划：
4. dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false
5. 当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
当s[i]与s[j]相等时

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是回文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

遍历顺序—>dp[i + 1][j - 1] 从下向上从左到右

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<int>>dp(n, vector<int>(n, 0));
        int cnt=0;
        for(int i=s.size()-1; i>=0; i--){
            for(int j=i; j<n; j++){
                if(s[i]==s[j]){
                    if(j-i<=1){
                         dp[i][j] = 1;
                         cnt++;
                    }else{
                        if(dp[i+1][j-1]==1){
                                dp[i][j] = 1;
                                cnt++;
                        }
                    }
                }
              
            }
        }
    return cnt;
    }
};

5. 最长回文子串

在判断回文子串的基础上，记录起始位置以及长度。

class Solution {
public:
    string longestPalindrome(string s) {
        int result = 1;
        int new_i =0;
        int n = s.size();
        vector<vector<int>>dp(n, vector<int>(n, 0));
        for(int i=n-1; i>=0; i--){
            for(int j=i; j<n; j++){
                if(s[i] == s[j] && (j-i<=1 || dp[i+1][j-1]==1)){
                    dp[i][j] = 1;
                    if(result <j-i+1){
                        result = j-i+1;
                        new_i =i;
                    }
                  
                }
            }
        }
        return s.substr(new_i, result);
    
    }
};

516. 最长回文子序列
相比于最长回文子串，回文子序列不考虑连续，可以进行删减。

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
递推公式
当s[i]与s[j]相等时 dp[i][j] = dp[i+1][j-1] + 2;
当s[i]与s[j]不相等时删去最前面或者删去最后取最大 dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
递推顺序：从下到上从左到右
初始化：递推公式是计算不到 i 和j相同时候的情况。所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>>dp(n, vector<int>(n, 0));
        for(int i=0; i<n; i++) dp[i][i] = 1;
        for(int i=n-1; i>=0; i--){
            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];
    }
};

思路2 1.s与s.reverse()的最长公共子序列即为其最长回文子序列文章来源地址https://www.toymoban.com/news/detail-614856.html

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string text_1 = s;
        reverse(s.begin(), s.end());
        string text_2 = s;
        int n = s.size();
        vector<vector<int>>dp(n+1, vector<int>(n+1, 0));
     
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(text_1[i] == text_2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        return dp[n][n];
    }
};