LeetCode32 Longest Valid Parentheses

题目：

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. (Hard)

分析：

题意是找到最长的合法括号字串。

看着就很想动态规划的题目，但是开始考虑的是dp[i][j]记录i到j是否是合法串。但是递推关系没法找。

想到应该是符合单序列动态规划的情况，用dp[i]表示以i结尾的最长合法括号串的长度。

递推关系如下：

如果 s[i] == '(' 则 dp[i] = 0;

如果 s[i] == ')' 则

　　如果 s[i - 1] == '(' 则 dp[i] = dp[i - 2] + 2;

　　如果 s[i - 1] == ')' 则需要记录 j = dp[i - 1]，并判断 s[i - 1 - j] 也就是从后往前数第一个不符合的字符的情况。

　　　　　　　　如果s[i - 1- j] == '(' 则 dp[i] = dp[i - j -2] + dp[i - 1] + 2； // i-j-2位置向前合法的，加上i-1位置向前合法的，加上s[i-j-1]和s[i]配对的2;

　　　　　　　　如果s[i - 1 - j]不存在或者为 ')' 则 s[i] = 0;

求出不等于0的dp[i]时更新result。

把上述递推关系实现代码如下：

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         if (s.size() == 0 || s.size() == 1) {
 5             return 0;
 6         }
 7         int result = 0;
 8         int dp[s.size()] = {0};
 9         if (s[1] == ')' && s[0] == '(') {
10             dp[1] = 2;
11             result = 2;
12         } 
13         for (int i = 1; i < s.size(); ++i) {
14             if (s[i] == '(') {
15                 dp[i] = 0;
16             }
17             if (s[i] == ')') {
18                 if (s[i - 1] == '(') {
19                     dp[i] = dp[i - 2] + 2;
20                     result = max(result,dp[i]);
21                 }
22                 if (s[i - 1] == ')') {
23                     int j = dp[i - 1];
24                     if (i - j - 1 >= 0 && s[i - j - 1] == '(') {
25                         dp[i] = dp[i - 1] + dp[i - j - 2] + 2;
26                         result = max(result,dp[i]);
27                     }
28                     else {
29                         dp[i] = 0;
30                     }
31                 }
32             }
33         }
34         return result;
35     }
36 };