【面试算法——动态规划 19】最长回文子序列&& （hard）让字符串成为回文串的最少插入次数

516. 最长回文子序列

链接: 516. 最长回文子序列

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

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

示例 1：

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

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

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

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] =0 。
对于第⼀种边界情况，我们在填表的时候，就可以同步处理。
对于第⼆种边界情况， dp[i + 1][j - 1] 的值为 0 ，不会影响最终的结果，因此可以不⽤考虑。

4. 填表顺序
因此我们的填表顺序应该是「从下往上填写每⼀⾏」，「每⼀⾏从左往右」

5. 返回值
需要返回dp[0][n - 1]

代码：

 int longestPalindromeSubseq(string s) {
          int n=s.size();
        

        //表示 i~j中最长子序列的长度
        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];

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

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

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

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

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

示例 1：

输入：s = “zzazz”
输出：0
解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。
示例 2：

输入：s = “mbadm”
输出：2
解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
示例 3：

输入：s = “leetcode”
输出：5
解释：插入 5 个字符后字符串变为 “leetcodocteel” 。

1.状态表示*
. 状态表⽰：
关于「单个字符串」问题中的「回⽂⼦序列」，或者「回⽂⼦串」，我们的状态表⽰研究的对象⼀般都是选取原字符串中的⼀段区域 [i, j] 内部的情况。这⾥我们继续选取字符串中的⼀段区域来研究：
dp[i][j] 表⽰：s字符串 [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. 填表顺序
因此我们的填表顺序应该是「从下往上填写每⼀⾏」，「每⼀⾏从左往右」

5. 返回值
需要返回dp[0][n - 1]

代码：

 int minInsertions(string s) {
          int n=s.size();

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


    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23