Longest Palindromic Subsequence
LeetCode 516.
Use dp[i][j] denote the length of the longest palindrome subsequence in the subscript range [i, j] of the string s.
when i < j
if s[i] = s[j]
dp[i][j] = dp[i+1][j - 1] + 2;
if s[i] != s[j]
dp[i][j] = Math.max(dp[i+1][j],dp[i][j - 1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestPalindromeSubseq(String s) {
if(s == null || s.length() == 0)
return 0;
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
char a = s.charAt(i);
for(int j = i + 1; j < n;j++){
char b = s.charAt(j);
if(a == b){
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];
}
}
|
