LeetCode之“动态规划”：Valid Parentheses && Longest Valid Parentheses

　 1. Valid Parentheses

　　题目要求：

　　Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

　　The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

　　这个题用‘栈’这种数据结构解决是比较方便的。程序如下：

 1 class Solution {
 2 public:
 3     bool isValidPar(char left, char right)
 4     {
 5         if (left == '(' && right == ')')
 6             return true;
 7         if (left == '[' && right == ']')
 8             return true;
 9         if (left == '{' && right == '}')
10             return true;
11     
12         return false;
13     }
14     
15     bool isValid(string s) {
16         int sz = s.size();
17         stack<char> left;
18         for(int i = 0; i < sz; i++)
19         {
20             char c = s[i];
21             if(c == '(' || c == '[' || c == '{')
22                 left.push(s[i]);
23             else
24             {
25                 if(left.size() == 0)
26                     return false;
27                     
28                 char top = left.top();
29                 if(!isValidPar(top, c))
30                     return false;
31                     
32                 left.pop();
33             }
34         }
35         
36         return left.size() == 0;
37     }
38 };

　 2. 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.

　　此文的动态规划解法参考自一博文：

　 1. 状态

　　DP[i]：以s[i-1]为结尾的longest valid parentheses substring的长度。　　

　 2. 通项公式

　　s[i] = '('：
　　DP[i] = 0

　　s[i] = ')'：找i前一个字符的最长括号串DP[i]的前一个字符 j = i-2-DP[i-1]
　　DP[i] = DP[i-1] + 2 + DP[j]，如果j >=0，且s[j] = '('
　　DP[i] = 0，如果j<0，或s[j] = ')'

　　......... ( x x x x )
　　j i-2 i-1

　　证明：不存在j' < j，且s[j' : i]为valid parentheses substring。
　　假如存在这样的j'，则s[j'+1 : i-1]也valid。那么对于i-1来说：
　　( x x x x x
　　j' j'+1 i-1
　　这种情况下，i-1是不可能有比S[j'+1 : i-1]更长的valid parentheses substring的。

　 3. 计算方向

　　显然自左向右，且DP[0] = 0

　　具体代码如下：

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         int sz = s.size();
 5         if(sz < 2)
 6             return 0;
 7 
 8         int maxLen = 0;
 9         vector<int> dp(sz + 1, 0);
10         for(int i = 1; i < sz + 1; i++)
11         {
12             int j = i - 2 - dp[i - 1];
13             if(s[i - 1] == '(' || j < 0 || s[j] == ')')
14                 dp[i] = 0;
15             else
16             {
17                 dp[i] = dp[i - 1] + 2 + dp[j];
18                 maxLen = max(maxLen, dp[i]);
19             }
20         }
21         
22         return maxLen;
23     }
24 };