Leetcode 516. Longest Palindromic Subsequence

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".

Analysis:
The problem is similar to the longest palindromic substring. So we use dp[i][j] means from character i to j, the longest palindromic substring. 

Code (Java):

?

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

class Solution {     public int longestPalindromeSubseq(String s) {         if (s == null || s.length() == 0) {             return 0;         }                   int[][] dp = new int[s.length()][s.length()];         int maxLen = 0;         for (int i = s.length() - 1; i >= 0; i--) {             for (int j = i; j < s.length(); j++) {                 if (s.charAt(i) == s.charAt(j)) {                     if (j - i < 2) {                         dp[i][j] = j - i + 1;                     } else {                         dp[i][j] = 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;     } }