今日份題目：

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

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

示例1

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

示例2

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

提示

• 1 <= s.length <= 1000

• s 僅由小寫英文字母組成

題目思路

動態(tài)規(guī)劃，使用二維dp數(shù)組記錄[i,j]間的最大回文子序列長度。

開始的時候，我嘗試使用reverse ( s.begin ( ) , s.end ( ) )翻轉(zhuǎn)字符串判斷連續(xù)相同位置的最大長度，最后發(fā)現(xiàn)與這道題不同，這道題目允許跨某些字母滿足回文，所以放棄原來的想法，不過翻轉(zhuǎn)后再動態(tài)規(guī)劃或許也可以，歡迎感興趣的朋友試一下，評論區(qū)討論哦！

接下來繼續(xù)講這道題目的思路。

因為需要枚舉區(qū)間內(nèi)的最大長度，如果從前往后遍歷，開始的區(qū)間跨度太大，可以理解為第一次判斷就得出最后返回的結(jié)果，肯定是不對的，所以是從最后位置開始遍歷i，j就是i+1到最后。然后，回文要滿足兩頭的字母一樣，所以對遍歷出的每組i和j判斷字符是否相同，相同的話，就在原長度也就是i+1到j-1范圍內(nèi)的最大長度加上這兩個點的長度2；如果不同，當前點就更新為區(qū)間內(nèi)最大長度。最后返回0到長度-1范圍內(nèi)的最大長度即可。

接下來是比較關鍵和大家比較關心的狀態(tài)轉(zhuǎn)移方程：

if(i、j處的字符相同)
{
	dp[i][j]=dp[i+1][j-1]+2;//在原來長度的基礎上加上這兩個字符的長度
} 
else 兩頭的字符不同
{
	dp[i][j]=max(dp[i+1][j],dp[i][j-1]);//不需要加上這兩頭的字符，根據(jù)相鄰范圍的值更新
}

代碼

class Solution 
{
public:
    int longestPalindromeSubseq(string s) 
    {
        int n=s.size();
        int dp[2000][2000]={0};//表示[i,j]范圍內(nèi)的最長回文子序列的長度
        for(int i=n-1;i>=0;i--) 
        {
            dp[i][i]=1;//單獨一個字符，自己就是最長回文子序列
            char c1=s[i];
            for(int j=i+1;j<n;j++) 
            {
                char c2=s[j];
                if(c1==c2) //兩頭的字符相同
                {
                    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];//找到[0,n-1]的整個字符串中的最長回文子序列長度
    }
};

提交結(jié)果

?歡迎大家在評論區(qū)討論，如有不懂的代碼部分，歡迎在評論區(qū)留言！文章來源地址http://www.zghlxwxcb.cn/news/detail-641248.html

到了這里，關于每天一道leetcode：516. 最長回文子序列（動態(tài)規(guī)劃&中等）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！