c++--动态规划回文串问题

1.回文子串力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa

分析：

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

2.最长回文串力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s，找到 s 中最长的回文子串。

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

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"

分析：这道题和上一道题差不多，上一道题会做后，知道题自己思考下

class Solution {
public:
    string longestPalindrome(string s) 
    {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        
        int begin=0,len=0;
        //string s1;
        for(i=n-1;i>=0;i--)
        {
            for(j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j)
                        dp[i][j]=true;
                    else
                    {
                        dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                    }
                    if(dp[i][j] && j - i + 1 > len) 
                        len = j - i + 1, begin = i;
                }
            }
        }
      
        return s.substr(begin,len);

    }
};

3.回文串分割力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s ，如果可以将它分割成三个非空回文子字符串，那么返回 true ，否则返回 false 。

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

示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

分析：先把所有的回文子串找出来，然后寻找是否可以组成三段的

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

4.分割回文串2 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

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

示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1

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])
                {
                    if(i==j)
                        dp[i][j]=true;
                    else
                        dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                }
            }
        }
        vector<int> arr(n,0x3f3f3f3f);
        for(int i=0;i<n;i++)
        {
           if(dp[0][i]==true) arr[i]=0;
           else
           {
                for(int j=1;j<=i;j++)
                {
                    if(dp[j][i])
                    arr[i]=min(arr[i],arr[j-1]+1);
                }
           }
        }
        return arr[n-1];
    }
};

5.最长回文子序列力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

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

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

分析：关于「回⽂⼦序列」和「回⽂⼦串」的分析⽅式，⼀般都是⽐较固定的，都是选择这段区域的「左右端点」的字符情况来分析。因为如果⼀个序列是回⽂串的话，「去掉⾸尾两个元素之后依旧是回⽂串」，「⾸尾加上两个相同的元素之后也依旧是回⽂串」。因为，根据「⾸尾元素」的不同，可以分为下⾯两种情况：
i. 当⾸尾两个元素「相同」的时候，也就是 s[i] == s[j] ：那么 [i, j] 区间上的最⻓回⽂⼦序列，应该是 [i + 1, j - 1] 区间内的那个最⻓回⽂⼦序列⾸尾填上s[i] 和 s[j] ，此时 dp[i][j] = dp[i + 1][j - 1] + 2
ii. 当⾸尾两个元素不「相同」的时候，也就是 s[i] != s[j] ：此时这两个元素就不能同时添加在⼀个回⽂串的左右，那么我们就应该让 s[i] 单独加在⼀个序列的左边，或者让 s[j] 单独放在⼀个序列的右边，看看这两种情况下的最⼤值：
• 单独加⼊ s[i] 后的区间在 [i, j - 1] ，此时最⻓的回⽂序列的⻓度就是 dp[i][j - 1] ；
• 单独加⼊ s[j] 后的区间在 [i + 1, j] ，此时最⻓的回⽂序列的⻓度就是 dp[i+ 1][j] ；取两者的最⼤值，于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) 。
综上所述，状态转移⽅程为：
▪ 当 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])

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];
    }
};

6.让字符串成为回文串最小插入次数力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

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

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

示例 1：
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

分析：

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/85780.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！