AlgoPressAppearance
0516-最长回文子序列
https://leetcode.cn/problems/longest-palindromic-subsequence
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000 s 仅由小写英文字母组成
基本思路 【需要思考】
动态规划 dp[i,j] 表示从s[i..j]是否是回文串，dp[i,j] = dp[i+1,j-1] && s[i] == s[j]
在本题中，子序列表示可以删除不需要的字符
dp[i,j] 表示 s[i..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])
初始化： dp[i,i] = 1
注意：外层循环 n -> 0, 因为需要判断 i-1 的数据
参考代码
csharp
public class Solution {
public int LongestPalindromeSubseq(string s) {
int n = s.Length;
int[,] dp = new int[n,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] = Math.Max(dp[i+1,j],dp[i,j-1]);
}
}
}
return dp[0,n-1];
}
}
算法推演
s = "bbbab"
n = 5;
Round 1
i = 4
dp[4,4] = 1
Round 2
i = 3 --> a
j = 4 --> b
dp[3,3] = 1
s[i] != s[j]
dp[3,4] = max(dp[4,4],[3,3]) = 1
Round 3
i = 2 --> b
j = 3 --> a
dp[2,2] = 1
s[i] != s[j]
dp[2,3] = max(dp[3,3],dp[2,2]) = 1
j = 4 --> b
s[i] == s[j]
dp[2,4] = dp[3,3] + 2 = 3;
Round 4
i = 1 --> b
j = 2 --> b
dp[1,1] = 1
s[i] == s[j]
dp[1,2] = dp[2,1] + 2 = 2; //2位数的处理，非常巧妙，本来应该是发现 i+1=j 就直接是2，现在应该 dp[2,1] 是不存在的默认值为0，所以可以直接复用+2
====
s = "bbbc"
n = 4;
测试 max
Round 1
i = 3
dp[3,3] = 1
Round 2
i = 2 --> b
j = 3 --> c
dp[2,2] = 1
s[i] != s[j]
dp[2,3] = max(dp[3,3],dp[2,2]) = 1
Round 3
i = 1 --> b
j = 2 --> b
dp[1,1] = 1
s[i] == s[j]
dp[1,2] = dp[2,1]+ 2 = 2
i = 1 --> b
j = 3 --> c
s[i] != s[j]
dp[1,3] = max(dp[1,2],dp[2,3]) = 2
Round 4
i = 0 --> b
j = 1 --> b
s[i] == s[j]
dp[0,1] = dp[1,0] + 2 = 2;
j == 2 --> b
s[i] == s[j]
dp[0,2] = dp[1,1] + 2 = 3; //3位数的处理
为什么不能从前往后算?
因为 dp[i,j] 依赖 dp[i+1,j-1]，需要先计算出 i+1 的值
csharp
for(int i=0; i< n ;i++){
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] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
}
}
}
计算 dp[0,1] 的时候，如果s[i]!=s[j], 测试 dp[0,1] = max(dp[1,1],dp[0,0]) 但是 dp[1,1]还没有计算过
参考 ：将字符串翻转，然后求两个字符串的最长公共子序列就可以了 https://leetcode.cn/problems/longest-palindromic-subsequence/solution/zui-chang-hui-wen-zi-xu-lie-by-leetcode-hcjqp/
复习动规:20220515
动态规划求取回文串方法，注意因为可以删除字符表示回文，所以 dp 要定义为回文子串的长度，而不是 是否成为回文。
csharp
public class Solution {
public int LongestPalindromeSubseq(string s) {
//动态规划，判断是否回文，是回文则计算长度
int n = s.Length;
int[,] dp = new int[n,n]; //不能用是否回文来测试，用长度表示
int maxLen = 0;
for(int i=n-1; i>=0; i--){
for(int j=i;j<n;j++){
if(s[i] == s[j]){
dp[i,j] = j-i<=1 ? j-i+1 : dp[i+1,j-1] + 2;
}
else{
dp[i,j] = Math.Max(dp[i+1,j],dp[i,j-1]);
}
maxLen = Math.Max(maxLen,dp[i,j]);
}
}
return maxLen;
}
}