【leetcode hot 100 32】最长有效括号

错误解法：暴力解法，判断每一个字符的最长有效括号

class Solution {public int longestValidParentheses(String s) {Deque<Character> stack = new LinkedList<>();int n = s.length();int max= 0;int curr=0;for(int i=0;i<n;i++){if(s.charAt(i)=='('){stack.push(s.charAt(i));}if(s.charAt(i)==')'){if(!stack.isEmpty()&&stack.peek()=='('){stack.pop();curr+=2;max=Math.max(max,curr);}else{curr=0;if(!stack.isEmpty()){stack.clear();}}}}return max;}
}

错误原因：当我们判断到i=2时，无法清除curr=0

解法一：（动态规划）①定义：dp[i]表示下标为i结尾的最长有效括号数，dp[n] ②初始状态：dp[i]=0 ③状态转移方程

class Solution {public int longestValidParentheses(String s) {// 定义：dp[i]表示下标为i结尾的最长有效括号数，dp[n]// 初始状态：dp[i]=0// 状态转移方程：int n = s.length();int[] db = new int[n]; // db[i]表示以下标i结尾的最长有效括号int max= 0;for(int i=1;i<n;i++){if(s.charAt(i)==')'){// ++时，以2为单位，只要考虑‘）’if(s.charAt(i-1)=='('){// [i-1,i]是有效的，由于要求连续性，只要考虑i-2即可db[i] = (i-2>=0?db[i-2]:0)+2;}else{// 如果i的前一个不为‘(’，可能是已经和别人配对了// 要找已经配对前的是否是‘(’if(i-db[i-1]>0 && s.charAt(i-db[i-1]-1)=='('){// db[i] = (i-db[i-1]-1>=0?db[i-db[i-1]-1]:0)+2;// 要加上db[i-1]// 是i-db[i-1]-2而不是i-db[i-1]-1，已经用i-db[i-1]-1配对了，要看i-db[i-1]-2是否连续db[i] = db[i-1] + ((i-db[i-1]-2)>=0?db[i-db[i-1]-2]:0)+2;}}}max = Math.max(max, db[i]);}return max;}
}

注意：

• 动态规划要考虑：dp代表什么？dp初始状态？dp动态转移方程？
• 考虑的是以下标i字符结尾的最长有效括号的长度，所以要在过程中记录最大值max