Memorized DFS / Top Down DP
I did not see a top down approach, so I created one. \ndp[i] = longest valid parentheses ending at index i.\n\nStarting from the end of the string s, either cur
I did not see a top down approach, so I created one. \ndp[i] = longest valid parentheses ending at index `i`.\n\nStarting from the end of the string `s`, either current position is `(` when it means computation is done for the string ending at index `i`; \nor a more complex case where the current char is `)` when recursion needs to continue to find out `dp[i - 1]`. \n```\nif s[i] == \'(\':\n    dp[i] = 0\nelif s[i] == \')\':\n\tif  i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == \'(\':\n\t\t\tdp[i] = dp[ i - dp[i - 1] - 2] + 2 + dp[i - 1]\n\telse:\n\t\t\tdp[i] = 0\n```\n\nWe need to do the above for all index within string `s` because we have defined the `dp[i]` to mean such valid string to end in every index. \nAfter that we want to collect the longest of such valid parentheses. \n\nHence the final code for this top down approach:\n```\nimport functools\nclass Solution:\n    def __init__(self):\n        self.max = 0\n        \n    def longestValidParentheses(self, s: str) -> int:\n        \n        @functools.lru_cache(maxsize = None)\n        def dp(s, i):\n            if i < 0:\n                return 0\n\n            if s[i] == \'(\':\n                return 0\n\n            ans = 0\n            length = dp(s, i - 1)\n            if i - length - 1 >= 0 and s[i - length - 1] == \'(\':\n                ans = length + 2 + dp(s, i - length - 1 - 1)\n\n            self.max = max(self.max, ans)\n            return ans\n\n        for i in range(len(s)):\n            dp(s, i)\n            \n        return self.max\n```
['Dynamic Programming', 'Depth-First Search', 'Python']