【LeetCode热题100】【动态规划】最长有效括号

叶茂林

发布于 2024-04-20 11:06:29

710

发布于 2024-04-20 11:06:29

要找有效括号的最长子串，定义dp[i]是以s[i]为结尾的子串的最长长度，显然s[i]必须是），那就会有两种情况，对于s[i]=），如果s[i-1]=（，说明dp[i]应该是dp[i-2]+2，考虑到是...()这样的，那么状态转移方程为

dp[i] = dp[i - 2]+ 2

如果是...))这样的，也就是s[i-1]=），也就是套壳状态，那么s[i]必定需要对应一个s[j]=（来闭环，那么j是多少呢，j和i之间应该隔了dp[i-1]个，那么j应该等于i-dp[i-1]-1，dp[i]就应该是dp[i-1]+2再加上dp[j-1]，那么状态转移方程应该为

 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

还需要加上数组边界条件的判断

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size());
        int ans = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == ')') {
                if (s[i - 1] == '(')
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(')
                    dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-19，如有侵权请联系 cloudcommunity@tencent.com 删除