I despise these types of questions. Who likes dynamic programming anyways?Given a string s, find the longest palindromic subsequences length in s. You may assume that the maximum length of s is 1000.

So the approach is the following:

Observation 1.

each 1 character subsequence is a palindrome.

Track the longest palindrome in substring(i, j) (i < j) as an entry in a 2D array with (i,j).

Due to observation 1. all items in the diagonal [i == j] will be 1. Get that out of the way

Code: Select all

```
int[][] dp = new int[s.length()][s.length()];
for(int i=0;i<s.length();i++) {
dp[i][i] = 1;
}
```

1. [bb]bab, b[bb]ab, bb[ba]b, bbb[ab]

2. [bbb]ab, b[bba]b, bb[bab]

3. [bbba]b, b[bbab]

4. [bbbab]

at each iteration notice that the previous iteration will contain the longest palindromic subsequence seen before it.

E.g iteration 2, step 2 b[bba]b:

bba is not a palindrome so the longest palindrome yet is the max of (bb, ba). ba is not a palindrome but bb is so the length is 2.

at each iteration if the char(i) == char(j) then the length of the palindrome will increase by 2 and will be 2 + the length of the previous palindrome.

So the dynamic programming relation is:

Code: Select all

```
DP[i][j] = 1 if i == j
DP[i][j] = 2 + DP[i+1][j-1] if char[i] == char[j]
DP[i][j] = max(DP[i+1][j], DP[i][j-1])
```

Code: Select all

```
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
for(int i=0;i<s.length();i++) {
dp[i][i] = 1;
}
for(int d=1;d<s.length();d++) {
for(int j=d;j<s.length();j++) {
int i = j - d;
if (s.charAt(i) == s.charAt(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][s.length() - 1];
}
```

1 to len(input). j defines the end of the window, and i defines the start of the window.