Evolve from brute force to dp


  • 26
    1. O(2^n) Brute force. If the two ends of a string are the same, then they must be included in the longest palindrome subsequence. Otherwise, both ends cannot be included in the longest palindrome subsequence.
        int longestPalindromeSubseq(string s) {
            return longestPalindromeSubseq(0,s.size()-1,s); 
        }
        int longestPalindromeSubseq(int l, int r, string &s) {
            if(l==r) return 1;
            if(l>r) return 0;  //happens after "aa" 
            return s[l]==s[r] ? 2 + longestPalindromeSubseq(l+1,r-1, s) : 
                max(longestPalindromeSubseq(l+1,r, s),longestPalindromeSubseq(l,r-1, s)); 
        }
    
    1. O(n^2) Memoization
        int longestPalindromeSubseq(string s) {
            int n = s.size();
            vector<vector<int>> mem(n,vector<int>(n));
            return longestPalindromeSubseq(0,n-1, s,mem); 
        }
        int longestPalindromeSubseq(int l, int r, string &s, vector<vector<int>>& mem) {
            if(l==r) return 1;
            if(l>r) return 0;
            if(mem[l][r]) return mem[l][r];
            return mem[l][r] = s[l]==s[r] ? 2 + longestPalindromeSubseq(l+1,r-1, s,mem) : 
                max(longestPalindromeSubseq(l+1,r, s,mem),longestPalindromeSubseq(l,r-1, s,mem)); 
            
        }
    
    1. O(n^2) dp
        int longestPalindromeSubseq(string s) {
            int n = s.size();
            vector<vector<int>> dp(n+1,vector<int>(n));
            for(int i=0;i<n;i++) dp[1][i]=1;
            for(int i=2;i<=n;i++) //length
                for(int j=0;j<n-i+1;j++) {//start index 
                    dp[i][j] = s[j]==s[i+j-1]?2+dp[i-2][j+1]:max(dp[i-1][j],dp[i-1][j+1]);
            return dp[n][0]; 
        }
    
    1. O(n^2) time, O(n) space dp. In #3, the current row is computed from the previous 2 rows only. So we don't need to keep all the rows.
        int longestPalindromeSubseq(string s) {
            int n = s.size();
            vector<int> v0(n), v1(n,1), v(n), *i_2=&v0, *i_1=&v1, *i_=&v;
            for(int i=2;i<=n;i++) {//length
                for(int j=0;j<n-i+1;j++)//start index
                    i_->at(j) = s[j]==s[i+j-1]?2+i_2->at(j+1):max(i_1->at(j),i_1->at(j+1));
                swap(i_1,i_2);    
                swap(i_1,i_); //rotate i_2, i_1, i_
            }
            return i_1->at(0); 
        }
    

  • 0

    Thank you much for sharing!!!!
    It's really brilliant to use the pointer.
    I didn't know a pointer could be used in this way before: i_->at(j)
    Your post absolutely deserves more attention


  • 0
    W

    confused by this problem. Is the the longest palindromic subsequence for the string bbbab is bbb or bab, the length of which are 3?
    Why the given answer is bbbb, the length is 4?


  • 1

    @wodaxia Seems you confuse subsequence with substring. Check the definition of subsequence at problem 392


  • 0
    R

    Brilliant! Thanks for sharing! Here is my code inspired by yours

    int longestPalindromeSubseq(string s) {
            int i = 0, j = 0, n = s.size();
            if (n < 2) return n;
            vector<int> dp(n, 0), dp2(n, 0);
    
            for (i = n-1; i >= 0; --i)
            {
                dp[i] = 1;
                for (j = i + 1; j < n; ++j)
                {
                    dp[j] = s[i] == s[j] ? dp2[j-1] + 2 : max(dp2[j], dp[j-1]);
                }
                dp2.swap(dp);
                dp.clear();
            }
            return dp2[n-1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.