516.Longest Palindromic Subsequence

This question on LeetCode took me the whole night to solve, and it's another typical dynamic programming problem. It seems like I have been encountering a lot of DP problems lately.

Question

Solution

We create a 2D-array dp, where dp[i][j] contains the answer of the longest palindromic subsequence of the substring formed from index i to j in s. There are three conditions following:

1. i == j
   THe single-word substring length is always one
2. s[i] == s[j]
   If the first and the last characters match, we can include these two characters in the palindromic subsequence and add it to the longest palindromic subsequence formed using the substring from index i + 1 to j - 1
3. s[i] != s[j]
   If the first and the last characters do not match, we look for the longest palindromic subsequence in both the substrings formed after ignoring the first and last characters. We pick the maximum of these two

//Time complexity: O(n^2)
//Space complexity: O(n^2)
class Solution {
    public int longestPalindromeSubseq(String s) {
        if(s.length() < 2) {
            return s.length();
        }
        int[][] dp = new int[s.length()][s.length()];
        for(int i=s.length()-1;i>=0;i--) {
            dp[i][i] = 1;
            for(int j=i+1;j<s.length();j++) {
                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];
    }
}