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

题目链接：32. 最长有效括号 - 力扣（LeetCode）

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

代码语言：javascript复制

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]，那么状态转移方程应该为

代码语言：javascript复制

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

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

代码语言：javascript复制

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;
    }
};

dp int leetcode 动态规划 数组

0 人点赞