2002-两个回文子序列长度的最大乘积

给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大
。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。

请你返回两个回文子序列长度可以达到的 ** 最大乘积** 。

子序列
指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个
回文字符串 。

示例 1：

![example-1](https://assets.leetcode.com/uploads/2021/08/24/two-palindromic-
subsequences.png)

**输入：** s = "leetcodecom"
**输出：** 9
**解释：** 最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。
它们的乘积为 3 * 3 = 9 。

示例 2：

**输入：** s = "bb"
**输出：** 1
**解释：** 最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。
它们的乘积为 1 * 1 = 1 。

示例 3：

**输入：** s = "accbcaxxcxx"
**输出：** 25
**解释：** 最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。
它们的乘积为 5 * 5 = 25 。

提示：

• 2 <= s.length <= 12
• s 只含有小写英文字母。

对于位置i，两个子序列可以选择用或者不用

暴力做法，其它语言没准会超时。

class Solution {
public:
    int ans = 0;
    int maxProduct(string s) {
        string s1, s2;
        dfs(s, s1, s2, 0);
        return ans;
    }
    
    void dfs(string &s, string s1, string s2, int index) {
        if(check(s1) && check(s2)) ans = max(ans, int(s1.size() * s2.size()));
        if(index == s.size()) return;
        dfs(s, s1 + s[index], s2, index + 1);//子序列s1使用该字符
        dfs(s, s1, s2 + s[index], index + 1);//子序列s2使用该字符
        dfs(s, s1, s2, index + 1);//子序列都不使用该字符
    }
    
    bool check(string &s) {
        int l = 0, r = s.size() - 1;
        while(l < r) {
            if(s[l++] != s[r--]) return false;
        }
        return true;
    }
};

使用引用传递加快速度：

void dfs(string &s, string &s1, string &s2, int index) {
    if(check(s1) && check(s2)) ans = max(ans, int(s1.size() * s2.size()));
    if(index == s.size()) return;
    s1.push_back(s[index]);
    dfs(s, s1, s2, index + 1);
    s1.pop_back();
    s2.push_back(s[index]);
    dfs(s, s1, s2, index + 1);
    s2.pop_back();
    dfs(s, s1, s2, index + 1);
}