# LeetCode-516. Longest Palindromic Subsequence

## LeetCode-516. Longest Palindromic Subsequence

Posted by Jae on July 29, 2019

### 1、题目

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:

"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".


### 2、思路

#### 2.3 初始条件和边界情况

f[i][i] = 1

### 3、实现

public int longestPalindromeSubseq(String s) {
if (s == null || "".equals(s) || s.length() == 0){
return 0;
}
char[] ss = s.toCharArray();
int n = ss.length;

int[][] f = new int[n][n];
int i, j, len;
int ans = 0;
// 定义f[i][j]表示下标i-j的最长回文串长度
for (len = 0; len < n; len++){
for (i = 0; i+len < n; i++){
j = i+len;
if (len == 0){
f[i][j] = 1;
}else{
if (ss[i] == ss[j]){
f[i][j] = 2 + f[i+1][j-1];
}else{
f[i][j] = Math.max(f[i][j-1], f[i+1][j]);
}
}
ans = Math.max(ans, f[i][j]);
}
}
return ans;
}