[Python] short dp, explained
This is quite difficult problem, which can be solved with dymamic programming. As usual let us define dp[i] the length of the longest valid substring ending at 
This is quite difficult problem, which can be solved with dymamic programming. As usual let us define `dp[i]` the length of the longest valid substring ending at `i`-th index. We can have several cases now:\n1. If `i == -1`, it means we reached empty string, return `0`, answer for empty string. Also if `s[i] = (`, answer is also `0`, because no valid parantheses can end with `(`\n2. Now, we have case, when `s[i] = )`. Let us look at the previous element. If it is equal to `(`, then we have `()` as two last elements and we can return `dp(i-2) + 2`.\n3. Now consider the case, when `s[i-1] = )`, it means, that we have the following situation: `...))`. If we want to find the longest valid parentheses for `i`, first we need to deal with `i-1`. Define `P = i - dp(i-1) - 1`. Then we have the following situation:\n\n`...((.....))`\n\n`...P.......i`\n\nHere on the top is the structure of string and in the bottom are indexes. String from `P + 1` to `i - 1` indexes including is the longest valid parentheses endind with `i-1` place. What we can say about place `P`. If we have `)` element on this place, then we need to return `0`: in this case we have patten `...)(...))...` and we **know** that answer for `dp(P)` is equal to `0`: if it is not, what we considered was not the longest answer for `i-1`. And if answer for `dp(P)` is zero, than answer for `dp(i)` is zero as well.\nIn the case, when we have `...((.....))`, answer is `dp(i-1) + dp(P-1) + 2`. \n\n#### Complexity\nTime complexity is `O(n)`, space complexity as well.\n\n#### Code\n```python\nclass Solution:\n    def longestValidParentheses(self, s):\n        @lru_cache(None)\n        def dp(i):\n            if i == -1 or s[i] == "(": return 0\n            if i >= 1 and s[i-1:i+1] == "()": return dp(i-2) + 2\n            P = i - dp(i-1) - 1\n            if P >= 0 and s[P] == "(":\n                return dp(i-1) + dp(P-1) + 2\n            return 0\n            \n        return max(dp(i) for i in range(len(s))) if s else 0\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**\n
['Dynamic Programming']