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];}
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] :
- 那么 [i, j] 区间内成为回⽂⼦串的最少插⼊次数,取决于 [i + 1, j - 1] 区间
内成为回⽂⼦串的最少插⼊次数; - 若 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] :
- 此时可以在区间最右边补上⼀个 s[i] ,需要的最少插⼊次数是 [i + 1, j] 成为回
⽂⼦串的最少插⼊次数+本次插⼊,即 dp[i][j] = dp[i + 1][j] + 1 ; - 此时可以在区间最左边补上⼀个 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];}