Update 2002.Maximum-Product-of-the-Length-of-Two-Palindromic-Subsequences.cpp

wisdompeak · web-flow · commit 359b9ba7b3de · 2021-09-12T14:34:52.000-07:00
diff --git a/Bit_Manipulation/2002.Maximum-Product-of-the-Length-of-Two-Palindromic-Subsequences/2002.Maximum-Product-of-the-Length-of-Two-Palindromic-Subsequences.cpp b/Bit_Manipulation/2002.Maximum-Product-of-the-Length-of-Two-Palindromic-Subsequences/2002.Maximum-Product-of-the-Length-of-Two-Palindromic-Subsequences.cpp
@@ -1,60 +1,44 @@
-class Solution {
-    int dp[1<<12];
+class Solution {    
     unordered_map<int,int>memo;
 public:
-    bool isPalin(string&s, int state)
+    int lp(string&s, int state)
     {
         if (memo.find(state)!=memo.end())
             return memo[state];
-        
-        vector<int>idx;
-        int n = s.size();
-        for (int i=0; i<n; i++)
+                        
+        string t;
+        for (int i=0; i<s.size(); i++)
         {
             if ((state>>i)&1)
-                idx.push_back(n-1-i);
+                t.push_back(s[s.size()-1-i]);
         }
-        reverse(idx.begin(), idx.end());
-        
-        int i=0, j=idx.size()-1;
-        while (i<j)
-        {
-            if (s[idx[i]]!=s[idx[j]])
+                
+        int n = t.size();          
+        vector<vector<int>>dp(n, vector<int>(n));
+        for (int i=0; i<n; i++)
+            dp[i][i] = 1;
+        for (int len=2; len<=n; len++)
+            for (int i=0; i+len-1<n; i++)
             {
-                memo[state]=0;
-                return false;
-            }                
-            i++;
-            j--;
-        }
-        memo[state]=1;
-        return true;
+                int j = i+len-1;
+                if (t[i]==t[j])
+                    dp[i][j] = dp[i+1][j-1]+2;
+                else
+                    dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
+            }        
+       
+        memo[state] = dp[0][n-1];
+        return dp[0][n-1];
     }
     
     
     int maxProduct(string s) 
     {
         int n = s.size();
-        
-        for (int state=1; state<(1<<n); state++)
-        {
-            int t = __builtin_popcount(state);
-            if (isPalin(s, state))
-            {
-                dp[state] = t;
-                continue;
-            }
-            for (int i=0; i<n; i++)
-            {
-                if ((state>>i)&1)                
-                    dp[state] = max(dp[state], dp[state-(1<<i)]);                
-            }
-        }        
-        
         int all = (1<<n)-1;
         int ret = 0;
-        for (int subset=1; subset<(1<<n); subset++)
-            ret = max(ret, dp[all-subset]*dp[subset]);
-        return ret;        
+        for (int subset=1; subset<(1<<n)-1; subset++)
+            ret = max(ret, lp(s, all-subset)*lp(s, subset));
+        return ret;
     }
 };
