516. Longest Palindromic Subsequence

Problem:

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:
dp[i][j] mean longest Palindromic  subsequence from index i to j in s.

Solution:
The reason i starts from len - 1 is that dp[i][j] depends on dp[i + 1][j - 1]. So we need to calc i + 1 and j - 1 first. 

1:  class Solution {  
2:    public int longestPalindromeSubseq(String s) {  
3:            int len = s.length();  
4:            int[][] dp = new int[len][len];  
5:            for (int i = len - 1; i >= 0; i--) {  
6:                 dp[i][i] = 1;  
7:                 for (int j = i + 1; j < len; j++) {  
8:                      if (s.charAt(i) == s.charAt(j))   
9:                           dp[i][j] = dp[i + 1][j - 1] + 2;  
10:                      else   
11:                           dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);  
12:                 }  
13:            }     
14:            return dp[0][len - 1];   
15:    }  
16:  }