Longest Valid Parentheses

问题 :https://leetcode-cn.com/problems/longest-valid-parentheses/

解:https://gitee.com/footmanff/leetcode/blob/master/src/main/java/com/footmanff/leetcode/dp/P32.java

解:使用动态规划。

问题实际上是求最长的「有效括号集」。

子问题定义:将输入定义为一个 char 数组 s,每个子问题定义为「已某个数组元素为结尾有效括号序列」。

定义数组 dp,dp[i] 为以 s[i] 为结尾的有效括号序列,比如 s 为 「(」「(」「)」「)」,那么 dp[3] 就是 2,因为数组第三个元素作为结尾的话,只有一组括号对有效,长度为 2。

转移函数:思考如果已知 dp[1] .. dp[i -1],需要求 dp[i],如何求解。

dp[i] 相对于 dp[i -1] 只是在末尾附加一个括号而已,是可以求解的:

  • 如果 s[i] 为 ‘(’ 直接设 dp[i] 为 0;

  • 如果 s[i] 为 ‘)’,取 s [i - 1],如果 s [i - 1] 为 ‘(‘,刚好和新添加的括号组成对,dp[i] 即为 dp[i-2] + 2,新组成的括号对长度为 2;

    • 如果 s [i - 1] 为 ‘)’,并且 dp[i- 1] 如果非 0 的话,取数组 s 的下标为 i - dp[i- 1] - 1 位置的字符,如果为 ‘(‘ ,那么刚好也和新添加的括号组成括号对,dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2。

      其中 dp[i - dp[i - 1] - 2] 是指配对的 ‘(‘ 之前的有效括号长度,有可能连接上的之前的有效括号。

边界处理需要注意,要多想几组数据测试。

还有其他的方式,比如栈。

资料

思路:https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-si-lu-xiang-jie-c-by-zhanganan042/