简介：最长回文子序列，LPS , dp
2 动态规划设计
2.7 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
1
2
3
|
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
|
示例 2：
1
2
3
|
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
|
提示：
- 1 <= s.length <= 1000
- s 仅由小写英文字母组成
解法一
动态规划
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
26
27
28
|
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
char[] chs = s.toCharArray();
int ans = 1;
//dp
//dp数组定义：dp[i][j]表示s[i~j]的LPS值
int[][] dp = new int[n][n];
//base case: i==j 时，只有一个字符，LPS是1
for(int i = 0; i < n; i++) {
dp[i][i] = 1;
}
//状态转移方程
for(int i = n-2; i >= 0; i--) {
for(int j = i + 1; j < n; j++) {
if(chs[i] == chs[j]) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
}
ans = Math.max(ans, dp[i][j]);
}
}
//返回值
return ans;
}
}
|
解法二
不难发现：dp[i][j]仅仅与dp[i+1][j-1],dp[i][j-1],dp[i+1][j]的状态有关，所以可以进行状态压缩，减小空间复杂度
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
26
27
28
29
|
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
char[] chs = s.toCharArray();
int ans = 1;
//dp
//dp数组定义：dp[j]表示s[i~j]的LPS值
int[] dp = new int[n];
int[] pre = new int[n];
//base case: i==j 时，只有一个字符，LPS是1
pre[n-1] = 1;
//状态转移方程
for(int i = n-2; i >= 0; i--) {
dp[i] = 1;
for(int j = i + 1; j < n; j++) {
if(chs[i] == chs[j]) {
dp[j] = pre[j-1] + 2;
} else {
dp[j] = Math.max(dp[j-1], pre[j]);
}
ans = Math.max(ans, dp[j]);
}
pre = Arrays.copyOf(dp, n);
}
//返回值
return ans;
}
}
|
