一，最長回文串

1.題目

給你一個(gè)字符串?s?，找出其中最長的回文子序列，并返回該序列的長度。

子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個(gè)序列。

示例 1：

輸入：s = "bbbab"
輸出：4
解釋：一個(gè)可能的最長回文子序列為 "bbbb" 。

示例 2：

輸入：s = "cbbd"
輸出：2
解釋：一個(gè)可能的最長回文子序列為 "bb" 。

提示：

• 1 <= s.length <= 1000
• s?僅由小寫英文字母組成

2.題目接口

class Solution {
public:
    int longestPalindromeSubseq(string s) {

    }
};

?3.解題思路及其代碼

? ? ? 在思考這道題時(shí)，我們先想到的可能是dp[i]來作狀態(tài)轉(zhuǎn)移方程,表示以第i個(gè)位置為結(jié)尾的最長回文子序列。但是，我們是不能這樣定義的。因?yàn)榈趇個(gè)位置能不能加入到這個(gè)子序列中是要看當(dāng)前子序列的開頭位置的字符是否與之匹配的。

? ? ? 在弄明白拋棄掉這種想法以后，我們便可以試著以區(qū)間dp的方式來解決：

1.狀態(tài)表示：dp[i][j]，表示在區(qū)間[i,j]的最長子序列。

2.狀態(tài)轉(zhuǎn)移方程：對于狀態(tài)轉(zhuǎn)移方程的推導(dǎo)需要分類討論，分類如下：

在第二種情況下dp[i][j]要等于在這三種情況下的最大值，又因?yàn)閐p[i+1][j-1]其實(shí)是在剩下的兩種情況中包含的，所以dp[i][j] = max(dp[i+1][j],dp[i][j-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--)//因?yàn)橛衐p[i][j] = dp[i+1][j]的情況，所以要從下到上初始化
        {
            for(int j = i;j<n;j++)//j>=i
            {
               if(s[i] == s[j])//第一種情況
               {
                   if(j>i) dp[i][j] = dp[i+1][j-1]+2;//j>i才能加2
                   else dp[i][j] = 1;//i == j，個(gè)數(shù)為1
               }
               else//第二種情況
               {
                   dp[i][j] = max(dp[i+1][j],dp[i][j-1]);//不用擔(dān)心越界的情況，因?yàn)楫?dāng)j == 0時(shí)
                                                         //i一定等于0，所以會(huì)在第一種情況中處理
               }
            }
        }

       return dp[0][n-1];
    }

};

二，讓字符串成為回文串的最小插入次數(shù)

1，題目

1312.?讓字符串成為回文串的最少插入次數(shù)

提示

困難

218

相關(guān)企業(yè)

給你一個(gè)字符串?s?，每一次操作你都可以在字符串的任意位置插入任意字符。

請你返回讓?s?成為回文串的?最少操作次數(shù)?。

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

示例 1：

輸入：s = "zzazz"
輸出：0
解釋：字符串 "zzazz" 已經(jīng)是回文串了，所以不需要做任何插入操作。

示例 2：

輸入：s = "mbadm"
輸出：2
解釋：字符串可變?yōu)?"mbdadbm" 或者 "mdbabdm" 。

示例 3：

輸入：s = "leetcode"
輸出：5
解釋：插入 5 個(gè)字符后字符串變?yōu)?"leetcodocteel" 。

提示：

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

2.題目接口

class Solution {
public:
    int minInsertions(string s) {

    }
};

3.解題思路及其代碼

對于這種回文串問題，因?yàn)橛辛松厦娴亩x狀態(tài)表示的經(jīng)驗(yàn)所以還是使用一個(gè)二維的dp表解決問題。

1.狀態(tài)表示：dp[i][j]表示在[i,j]這個(gè)區(qū)間內(nèi)使這個(gè)區(qū)間內(nèi)的字符串成為回文串的最小插入次數(shù)。

2.狀態(tài)轉(zhuǎn)移方程：在這里狀態(tài)轉(zhuǎn)移方程還是要分類討論，還是要看s[i]，s[j]是否相等：

在第二種情況下要取兩者的較小值。

代碼：

由以上思路寫出代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-766773.html

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--)//有dp[i][j] = dp[i+1][j]+1的情況，所以要從下到上遍歷
         {
            for(int j = i;j<n;j++)
            {
                if(s[i] == s[j])
                {
                    if(j>i) dp[i][j] = dp[i+1][j-1];//只有一個(gè)字符不用搞了
                }
                else
                {
                    dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
         }

         return dp[0][n-1];

    }
};

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃學(xué)習(xí)——最長回文子序列，讓字符串變成回文串的最小插入次數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！