动态规划最好理解
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;