[Java] FROM top-down w/ memo TO bottom-up dp | Beats 100%
Since the tag of this problem is Dynamic Programming, here I shared a top down approach, similar to solution 2 but for me it\'s easier to understand. \n\nWe def
Since the tag of this problem is `Dynamic Programming`, here I shared a top down approach, similar to solution 2 but for me it\'s easier to understand. \n\nWe define the subproblem as `dp(idx) := length of the longest valid parentheses which use s[idx] as end.`\n\nWe only compute when `s[idx] == \')\'` since `\'(\'` can\'t be the end of a valid parentheses.\n\nThe recurrence relationship is:\n1. when `s[idx - 1] == \'(\'`:\n\t `\'(\'` and `\')\'` at idx - 1 and idx respectively already form a valid `()`, since we want to form the longest substring, we want to check if the substring end with `s[idx - 2]` is also valid, if valid, we need to add the length of it (`dp(idx - 2)`).\n\t `dp(idx) = 2 + dp(idx - 2)`\n2. when `s[idx - 1] == \')\'`:\n\t\tfirst we need to check if substring end at `idx - 1` is valid, if not. then we can\'t use `idx` as end neither. if valid, we want to make sure that `)` at `idx` has a `\'(\'` to match it, without this `\'(\'`, substring end at `idx` can\'t be valid as well. So what\'s the position should such `\'(\'` located? Its position is at `idx - dp(idx - 1) - 1`, e.g. `....(  (())  )`, previous valid parentheses length is 4, so the `\'(\'` matching `\')\'` at idx is at `idx - 4 - 1`, where `4 = dp(idx - 1)`. as in case 1, we want to check if the substring can be longer, so we check the previous index which is left to the `\'(\'` that match `\')\'` at idx. Its index is `idx - dp(idx - 1) - 2`.\n\t\t`if dp(idx - 1) > 0 && s[idx - dp(idx - 1) - 1] == \'(\':        dp(idx) = 2 + dp(idx - 1) + dp(idx - dp(idx - 1) - 2)`\n\nBase case is trivial, `dp(idx) = 0 if idx <= 0`\n\n```\nclass Solution {\n    int[] memo;\n    \n    public int longestValidParentheses(String s) {\n        int n = s.length();\n        int ans = 0;\n        memo = new int[n];\n        Arrays.fill(memo, -1);\n        for (int i = 0; i < n; i++) {\n            ans = Math.max(ans, dp(s, i));\n        }\n        return ans;\n    }\n    \n    private int dp(String s, int idx) {\n        if (idx <= 0) return 0; // Base case\n        if (memo[idx] != -1) return memo[idx];\n\t\t\n        int ans = 0;\n        if (s.charAt(idx) == \')\') {\n            if (idx > 0 && s.charAt(idx - 1) == \'(\') {\n                ans += 2; // \'(\' \')\' at idx-1 and idx\n                ans += dp(s, idx - 2); // previous valid length\n            } else if (idx > 0 && s.charAt(idx - 1) == \')\') {\n                int prevLen = dp(s, idx - 1); // idx-1 has valid parentheses?\n                if (prevLen > 0 && idx - prevLen - 1 >= 0 && s.charAt(idx- prevLen - 1) == \'(\') {\n                    ans += 2; // \'(\' pair with \')\' at idx\n                    ans += prevLen; // length use s[idx -1] as end\n                    ans += dp(s, idx - prevLen - 2); // more previous length\n                }\n            }\n        }\n        memo[idx] = ans;\n        return ans;\n    }\n}\n```\n\nIf you understand this top-down approach, you can easily convert it to bottom-up dp to avoid recursive calls.\n```\n    public int longestValidParentheses(String s) {\n        int n = s.length();\n        int[] dp = new int[n];\n        int ans = 0;\n        \n        for (int i = 1; i < n; i++) {\n            if (s.charAt(i) == \')\') {\n                if (s.charAt(i - 1) == \'(\') {\n                    dp[i] = 2 + (i - 2 >= 0 ? dp[i - 2] : 0);\n                } else {\n                    int prevLen = dp[i - 1];\n                    if (prevLen > 0 && i - prevLen - 1 >= 0 && s.charAt(i - prevLen - 1) == \'(\') {\n                        dp[i] = 2 + prevLen + (i - prevLen - 2 >= 0 ? dp[i - prevLen - 2] : 0);\n                    }\n                }\n            }\n            ans = Math.max(ans, dp[i]);\n        }\n\n        return ans;\n    }\n```\n\nTime Complexity: `O(n)`\nSpace: `O(n)`
['Dynamic Programming', 'Java']