写在前面

递推公式难分析的DP问题是真的挺难的，想了好久也没有想出来怎么做(除了暴力。。。)，还是很需要练习啊。

题目

核心思路

LeetCode的20. 有效的括号相对来说就很简单，因为只用遍历一次看括号是否有效，不过这道题要求出最长的有效括号，涉及到字符串的子串，就变得很难了，因为可能性真的很多。
首先，暴力法就不多说了，遍历每一种可能的子串，然后对每个子串判断是否是有效的即可。时间复杂度O(n³)，提交会在227个用例超时。
然后就是重头戏动态规划了。既然用动态规划，那该有的步骤当然不能少。

子问题

既然要求的是有效括号，那么最小的有效括号很容易可以想到 ： ()，如果想保证括号仍然是有效的，那么可以在这个最小的基础上后边加若干对括号，或者外边套若干层括号，即 ()()()、((()))。对任意有效括号子串，都可以有这两种扩展的方式，这也就算是找到了子问题。

定义DP数组

有了子问题，就要定义dp数组了，也就是局部的最优解，由于最后要求的是最长的有效括号，同时，为了不漏掉所有情况，那么 dp[i] 就可以表示以i下标位置结尾的最长有效括号。并且要保留全局最优解，所以每计算一次dp[i]就要比较留下最大值。

状态转移公式

虽然前边可能很顺利能想到，但是这道题的状态转移公式是真的难想。
根据前边DP数组的定义，dp[i]会面对两种情况：
(1)s.chatAt(i) == '(' (2)s.charAt(i) == ')'

1. 首先来讨论第一种情况，字符串以'('结尾，显然该字符串不可能是有效的，所以在这时 dp[i] = 0;
2. 然后来看第二种情况，对于以')'结尾的字符串，他有三种情况：
   (1)i == 0 即字符串的第一个字符是')'(2)s.charAt(i - 1) == '('(3)s.charAt(i - 1) == ')'

• 第一种情况很显然， dp[i] = 0，联合上边的情况，也就是说无论第一个字符是什么，dp[0] = 0；
• 接下来看第二种情况，当前字符与前一个字符构成了一对有效括号，通过上边子问题的叙述就可以知道，相当于在dp[i - 2]的后边加了一对有效括号，很容易想到dp[i] = dp[i - 2] + 2;
• 接下来是第三种情况，也是最难想的一种情况，即可能发生了嵌套，如果发生了嵌套，也就是说dp[i - 1]对应的有效字符串的外层嵌套了一层括号，那么就要考虑它的外层最左端是否是'('，是的话算嵌套，dp[i] = dp[i - 1] + 2，不是的话直接等于0.很容易就会这样想，但是这样想其实是有漏洞的，我们来看下边的图例： 可以看到，对于dp[6]，如果直接使用 dp[6] = dp[5] + 2; 得到的是红圈部分的有效括号，并没有考虑他前边可能还连接着若干对括号，所以为了考虑这部分，要在原有公式的基础上加上与当前')'匹配的左括号再左边的dp值，即：dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]当然还要防止越界，加一个判断即可。

动态规划代码

class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length() + 1];
        for (int i = 2; i < dp.length; i++) {
            if (s.charAt(i - 1) == '(') {
                continue;
            }
            if (s.charAt(i - 2) == '(') {
                dp[i] = dp[i - 2] + 2;
            } else {
                dp[i] = (i - 2 - dp[i - 1] >= 0) && s.charAt(i - 1 - dp[i - 1] - 1) == '(' ? dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]] : 0;
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

总结

这道题的递推公式真的难想到，而且还要注意很多细节，真的是很难的一道DP题了，另外官方题解还有两种方法，一种是用栈，要注意保留每个有效括号串最开始位置的下标；还有一种使用双指针，注意不满足条件时将left和right的值归零即可。本人还是菜鸡一枚正在努力学习，有错误或者写的不合适的地方还请指出，感恩相遇~