错误解法:暴力解法,判断每一个字符的最长有效括号
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) {int n = s.length();int[] db = new int[n]; int max= 0;for(int i=1;i<n;i++){if(s.charAt(i)==')'){if(s.charAt(i-1)=='('){db[i] = (i-2>=0?db[i-2]:0)+2;}else{if(i-db[i-1]>0 && s.charAt(i-db[i-1]-1)=='('){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