Python DFS + Memorisation
Intuition: similar to LCS, we loop through every possible combination of parlimdromic subsequences, but also introduce two extra parameter, exclude which is the
Intuition: similar to LCS, we loop through every possible combination of parlimdromic subsequences, but also introduce two extra parameter, `exclude` which is the indexes of first palindromic subsequences, `num` indicating the number of palindromic subsequences e.g. 0 means first subsequence, 1 means second subsequence.\n\n\n```\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        n = len(s)\n        @cache\n        def dfs(i: int, j: int, exclude: Tuple[int], num: int) -> int:\n            if i > j:\n\t\t\t\t# we found the first palindromic subsequence, go start find the second one, then  return the product\n                if num == 0:\n                    ret = dfs(0, n-1, exclude, 1)\n                    return ret * len(exclude)\n                return 0\n            if num == 1 and i in exclude:\n                return dfs(i+1, j, exclude, num)\n            if num == 1 and j in exclude:\n                return dfs(i, j-1, exclude, num)\n            if s[i] == s[j]:\n                add = 1 if i == j else 2\n                e2 = exclude\n                if num == 0:\n                    if i == j:\n                        e2 = exclude + (i,)\n                    else:\n                        e2 = exclude + (i, j)\n\t\t\t\t\t# We only return the length of second subsequence, first subsequence length can be retrieved with len(exclude)\n                    add = 0\n                r1 = dfs(i+1, j-1, e2, num) + add\n\t\t\t\t# putting (n, 0) so we can treat the current exclude as the first subsequence, force dfs to start find the second subsequence\n                r2 = dfs(n, 0, e2, num)\n                r3 = dfs(n, 0, exclude + (j,), num)\n                r4 = dfs(n, 0, exclude + (i,), num)\n                r5 = dfs(i+1, j-1, exclude, num)\n                return max(r1, r2, r3, r4, r5)\n            else:\n                r1 = dfs(i+1, j, exclude, num)\n                r2 = dfs(i, j-1, exclude, num)\n                r3 = dfs(i+1, j-1, exclude, num)\n                r4 = dfs(n, 0, exclude + (j,), num)\n                r5 = dfs(n, 0, exclude + (i,), num)\n                return max(r1, r2, r3, r4, r5)\n            \n        return dfs(0, n - 1, tuple(), 0)\n```
['Depth-First Search', 'Python']