-
Notifications
You must be signed in to change notification settings - Fork 22
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
32. 最长有效括号 #50
Labels
Comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
原题链接
子问题
dp[i]: 表示以 s[i] 结尾的最长有效括号长度。
状态转移方程
分情况讨论出所有可能:
s[i] 可能为 '(' 或者 ')'
:s[i] === '('
时,不可能组成有效的括号,所以 dp[i] = 0。s[i] === ')'
时,需要查看 s[i - 1]。s[i - 1] === '('
时,s[i - 1] 和 s[i] 可以组成一对有效括号,需要查看 s[i - 2]。dp[i] = 2
dp[i] = dp[i - 2] 2
s[i - 1] === ')'
时,此时 s[i - 1] 和 s[i] 合起来是 '))',需要查看 s[i - dp[i - 1] - 1]。s[i - dp[i - 1] - 1]
不存在或为 ')',则 s[i] 找不到匹配,所以 dp[i] = 0。s[i - dp[i - 1] - 1]
是 '(',与 s[i] 匹配。此时需要查看 s[i - dp[i - 1] - 2]是否存在。s[i - dp[i - 1] - 2]
不存在,dp[i] = dp[i - 1] 2
s[i - dp[i - 1] - 2]
存在,dp[i] = dp[i - 1] dp[i - dp[i - 1] - 2] 2
用代码表示出来即可:
The text was updated successfully, but these errors were encountered: