# 2002. Maximum Product of the Length of Two Palindromic Subsequences
###### tags: `Leetcode` `Medium` `Bit Manipulation` `Dynamic Programming`
Link: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/
## 思路
将原字符串拆为两个subsequence。然后查看每个subsequence里面最长的回文子序列。

对于一个subsequence里面的最长回文子序列问题，我们可以将这个子序列收拢转化为一个常规的字符串。求字符串里的最长回文子序列，这是一个经典问题。可以用$O(N^2)$的DP。
## Code

class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        int all = (1<<n)-1;
        int ans = 0;
        for(int i=1; i<=all/2+1; i++){
            int len1 = computePalin(i, s);
            int len2 = computePalin(all-i, s);
            ans = Math.max(ans, len1*len2);
        }
        return ans;
    }
    private int computePalin(int mask, String s){
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<s.length(); i++){
            if(((mask>>i)&1)==1) sb.append(s.charAt(i));
        }
        
        int n = sb.length();
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
        }
        for(int len=2; len<=n; len++){
            for(int i=0; i<n; i++){
                int j = i+len-1;
                if(i+len-1>=n) continue;
                if(sb.charAt(i)==sb.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][n-1];
    }
}