516. Longest Palindromic Subsequence

Description

Solution

Use DP to find the longest palindromic subsequence in one interval

//dp[i][j] =  (i > j) from j to i, longest palinidromic subsequence
//dp[i][j] = dp[i-1][j+1] + 2 (if s[i] == s[j]), else dp[i][j] = dp[i][j+1]

Code

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        //dp[i][j] =  (i > j) from j to i, longest palinidromic subsequence
        //dp[i][j] = dp[i-1][j+1] + 2 (if s[i] == s[j]), else dp[i][j] = dp[i][j+1]
        vector<vector<int>> dp(s.size()+1, vector<int>(s.size()+1, 0));
        for(int i = 1; i <= s.size(); i++){
            for(int j = i; j > 0; j--){
                if(i == j)
                    dp[i][j] = 1;
                else{
                    if(s[i-1] == s[j-1])
                        dp[i][j] = dp[i-1][j+1] + 2;
                    else
                        dp[i][j] = max(dp[i][j+1], dp[i-1][j]);
                }
            }
        }
        return dp[s.size()][1];
    }
};