动态规划最好理解
dp[i]代表位置i结尾的最长括号子串
1.初始状态 0
2.转移方程
当前位置为(,直接返回0
当前位置为)
情况1:前一位置为(,则返回前前位置的值加2
情况2:前一位置为),
考虑这种情况()((())) 位置分别为0,1,2,3,4,5,6,7
当前位置为7 dp[i-dp[i-1]-2]代表位置1结尾的最长括号子串 dp[i-1]代表位置6结尾的最长子串,dp[i-1] = 4 dp[i]一般为dp[i-1]+2,但是因为匹配的字符前一位置i-dp[i-1]-2存在配对的话,也需要加上。 dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2];需要判断i-dp[i-1]-2 是大于等于0的数
3.返回结果
if(s.length() == 0){
return 0;
}
int ans = 0;
int dp[s.length()];
for(int i=0;i<s.length();i++){
dp[i] = 0;
if(i > 0 && s[i] == ')' ){
if(s[i-1] == '('){
dp[i] = (i == 1) ? 2 : dp[i-2] + 2;
}else if(s[i-dp[i-1]-1] == '('){
dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2];
}
}
ans = max(ans,dp[i]);
}
return ans;



京公网安备 11010502036488号