Dynamic Programming 1:Longest Valid Parentheses

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

简单说一下题意：
给定一个只包含"("或")"的字符串，找到括号格式正确的最长子字符串的长度，比如输入为"(()"时，输出为2，输入为")()())"输出为4。

此问题肯定需要遍历所有字符，遍历到一个")"时尽量利用前面获取到的信息进行配对，如果前面有能够匹配的到的"("，这里“能够匹配的到的”的意思是离其最近的没有配对的"("，那么根据前面的信息计算出当前位置最长有效子字符串的长度。计算的方法是：

我们使用n表示索引(0开始)，f(n)表示n位置字符参与的能够配对的子字符串长度，那么上一个没有配对的'('的位置为n - f(n-1) -2：

IMG_20180621_171404.jpg

根据推导公式实现的代码：

public class LongestValidParentheses {
    public static void main(String[] args) {
        System.out.println(new LongestValidParentheses()
                                   .longestValidParentheses2("()(())"));
    }

    int longestValidParentheses2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] lengthArr = new int[s.length()];

        int max = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')' && i - lengthArr[i - 1] - 1 >= 0 && s
                    .charAt(i - lengthArr[i - 1] - 1) == '(') {
                lengthArr[i] = lengthArr[i - 1] + 2 + (i - lengthArr[i - 1] -
                        2 > 0 ? lengthArr[i - lengthArr[i - 1] - 2] : 0);
            }
            max = Math.max(max, lengthArr[i]);
        }

        return max;
    }
}

看到有的解决方案是创建一个s.length()+1的数组，0位置为保留位置，这样就不用判断“i - lengthArr[i - 1] - 2 > 0”了。

现在贴上代码：

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