Problem

Longest Palindromic Subsequence

Approach

We can represent the LPS as following with DP[i][j]:

  • DP[i][j] = 1, if i == j
  • DP[i][j] = DP[i + 1][j - 1] + 2, if str[i] == str[j]
  • DP[i][j] = max(DP[i + 1][j], DP[i][j - 1]), otherwise
  • More importantly, DP[i][j] increase only when str[i] == str[j]and update its’ value from DP[i + 1][j - 1], not DP[i + 1][j] and DP[i][j - 1].

Code

class Solution {
    public int longestPalindromeSubseq(String s) {
        int N = s.length();
        int[][] dp = new int[N][N];
        int ans = 0;
        for(int i = 0; i < N; i ++){
            dp[i][i] = 1;
            ans = 1;
        }
        for(int len = 2; len <= N; len ++){
            for(int i = 0; i < N; i ++){
                int j = i + len - 1;
                if(j >= N) continue;
                if(i + 1 < N){
                    dp[i][j] = dp[i + 1][j];
                }
                if(dp[i][j - 1] > dp[i][j]){
                    dp[i][j] = dp[i][j - 1];
                }
                if(i + 1 < N && dp[i][j] < dp[i + 1][j - 1]){
                    dp[i][j] = dp[i + 1][j - 1];
                }
                if(i + 1 < N && s.charAt(i) == s.charAt(j) && dp[i][j] < 2 + dp[i + 1][j - 1]){
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}