【算法挨揍日记】day36——516. 最长回文子序列、1312. 让字符串成为回文串的最少插入次数

浅浅的花香味﹌ 2024-02-17 13:05 17阅读 0赞

## 516. 最长回文子序列 ##

[516. 最长回文子序列][516.]

### 题目描述： ###

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

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

![e518342c78ee42148f51076b91e9337e.png][]

### 解题思路： ###

算法思路：

1.  状态表⽰：

关于「单个字符串」问题中的「回⽂⼦序列」，或者「回⽂⼦串」，我们的状态表⽰研究的对象⼀

般都是选取原字符串中的⼀段区域  \[i, j\]  内部的情况。这⾥我们继续选取字符串中的⼀段区域

来研究：

dp\[i\]\[j\]  表⽰：s 字符串  \[i, j\]  区间内的所有的⼦序列中，最⻓的回⽂⼦序列的⻓度。

2.  状态转移⽅程：

关于「回⽂⼦序列」和「回⽂⼦串」的分析⽅式，⼀般都是⽐较固定的，都是选择这段区域的「左

右端点」的字符情况来分析。因为如果⼀个序列是回⽂串的话，「去掉⾸尾两个元素之后依旧是回

⽂串」，「⾸尾加上两个相同的元素之后也依旧是回⽂串」。因为，根据「⾸尾元素」的不同，可

以分为下⾯两种情况：

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\])

3.  初始化：

我们的初始化⼀般就是为了处理在状态转移的过程中，遇到的⼀些边界情况，因为我们需要根据状

态转移⽅程来分析哪些位置需要初始化。

根据状态转移⽅程  dp\[i\]\[j\] = dp\[i + 1\]\[j - 1\] + 2  ，我们状态表⽰的时候，选取的

是⼀段区间，因此需要要求左端点的值要⼩于等于右端点的值，因此会有两种边界情况：

i.  当  i == j  的时候，  i + 1  就会⼤于  j - 1  ，此时区间内只有⼀个字符。这个⽐较好

分析，  dp\[i\]\[j\]  表⽰⼀个字符的最⻓回⽂序列，⼀个字符能够⾃⼰组成回⽂串，因此此

时  dp\[i\]\[j\] = 1  ；

ii.  当  i + 1 == j  的时候，  i + 1  也会⼤于  j - 1  ，此时区间内有两个字符。这样也

好分析，当这两个字符相同的时候，  dp\[i\]\[j\] = 2  ；不相同的时候，  d\[i\]\[j\] =

。

对于第⼀

种

边界情况，我们在填表的时候，就可以同步处理。

对于第⼆种边界情况，  dp\[i + 1\]\[j - 1\]  的值为  0  ，不会影响最终的结果，因此可以不⽤

考虑。

4.  填表顺序：

根据「状态转移」，我们发现，在  dp  表所表⽰的矩阵中，  dp\[i + 1\]  表⽰下⼀⾏的位置，

dp\[j - 1\]  表⽰前⼀列的位置。因此我们的填表顺序应该是「从下往上填写每⼀⾏」，「每⼀

⾏从左往右」。

这个与我们⼀般的填写顺序不太⼀致。

5.  返回值：

根据「状态表⽰」，我们需要返回  \[0, n -1\]  区域上的最⻓回⽂序列的⻓度，因此需要返回

dp\[0\]\[n - 1\]  。

### 解题代码： ###

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])
                    {  
                        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][j-1],dp[i+1][j]);
                }
            }
            return dp[0][n-1];
        }
    };

## 1312. 让字符串成为回文串的最少插入次数 ##

[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

### 题目描述： ###

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

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

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

![584d5b5d99434454b8f76928b98bd1b0.png][]

### 解题思路： ###

算法思路：

1.  状态表⽰：

关于「单个字符串」问题中的「回⽂⼦序列」，或者「回⽂⼦串」，我们的状态表⽰研究的对象⼀

般都是选取原字符串中的⼀段区域  \[i, j\]  内部的情况。这⾥我们继续选取字符串中的⼀段区域

来研究：

状态表⽰：  dp\[i\]\[j\]  表⽰字符串  \[i, j\]  区域成为回⽂⼦串的最少插⼊次数。

2.  状态转移⽅程：

关于「回⽂⼦序列」和「回⽂⼦串」的分析⽅式，⼀般都是⽐较固定的，都是选择这段区域的「左

右端点」的字符情况来分析。因为如果⼀个序列是回⽂串的话，「去掉⾸尾两个元素之后依旧是回

⽂串」，「⾸尾加上两个相同的元素之后也依旧是回⽂串」。因为，根据「⾸尾元素」的不同，可

以分为下⾯两种情况：

i.  当⾸尾两个元素「相同」的时候，也就是  s\[i\] == s\[j\]  ：

1.  那么  \[i, j\]  区间内成为回⽂⼦串的最少插⼊次数，取决于  \[i + 1, j - 1\]  区间

内成为回⽂⼦串的最少插⼊次数；

2.  若  i == j  或  i == j - 1  （  \[i + 1, j - 1\]  不构成合法区间），此时只有 1

~ 2 个相同的字符，  \[i, j\]  区间⼀定是回⽂⼦串，成为回⽂⼦串的最少插⼊次数是

0。

此时

dp\[i\]\[j\] = i >= j - 1 ? 0 : dp\[i + 1\]\[j - 1\]

；

ii.  当⾸尾两个元素「不相同」的时候，也就是  s\[i\] != s\[j\]  ：

1.  此时可以在区间最右边补上⼀个  s\[i\]  ，需要的最少插⼊次数是  \[i + 1, j\]  成为回

⽂⼦串的最少插⼊次数 + 本次插⼊，即  dp\[i\]\[j\] = dp\[i + 1\]\[j\] + 1  ；

2.  此时可以在区间最左边补上⼀个  s\[j\]  ，需要的最少插⼊次数是  \[i, j + 1\]  成为回

⽂⼦串的最少插⼊次数 + 本次插⼊，即  dp\[i\]\[j\] = dp\[i\]\[j + 1\] + 1  ；

综上所述，状态转移⽅程为：

▪  当  s\[i\] == s\[j\]  时：  dp\[i\]\[j\] = i >= j - 1 ? 1 : dp\[i + 1\]\[j -

1\]

。

▪

当  s\[i\] != s\[j\]

时：  dp\[i\]\[j\] = min(dp\[i + 1\]\[j\], dp\[i\]\[j - 1\]) +

1  。

3.  初始化：

根据「状态转移⽅程」，没有不能递推表⽰的值。⽆需初始化。

4.  填表顺序：

根据「状态转移」，我们发现，在  dp  表所表⽰的矩阵中，  dp\[i + 1\]  表⽰下⼀⾏的位置，

dp\[j - 1\]  表⽰前⼀列的位置。因此我们的填表顺序应该是「从下往上填写每⼀⾏」，「每⼀

⾏从左往右」。

这个与我们⼀般的填写顺序不太⼀致。

### 解题代码： ###

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

[516.]: https://leetcode.cn/problems/longest-palindromic-subsequence/
[e518342c78ee42148f51076b91e9337e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/18c2af79d78c4851b686a320204b6405.png
[LeetCode_ -]: https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
[584d5b5d99434454b8f76928b98bd1b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/f5815ba62c6d45028b5bb46dbc7677b8.png