32.longest-valid-parentheses.md

32. 最长有效括号

1. 描述：给定一个只包含 '(' 和 ')' 的字符串s，找出最长的包含有效括号的子串的长度。
2. 回顾最值型DP解题步骤
   • 确定状态
     • 研究最优策略的最后一步
     • 化为子问题
   • 转移方程：根据子问题定义得到
   • 初始条件和边界情况
   • 计算顺序
3. 本题步骤
   • 定义数组DP.size = s.size，DP[i]初始值是0。
   • DP[i]表示以i结尾（从0开始）的字符串里的有效括号长度。
   • 转移方程
     • 如果s[i]=='(', 不管i之前是什么括号，dp[i]=0。
     • 如果s[i]==')', 此时分2种情况👇(有两张图示)
       • s[i-1]=='('，则dp[i] = dp[i-2]+2
       • s[i-1]==')'，并且i-1之前有有效括号长度，即i-1的对称位置i-dp[i-1]是'('，并且i的对称位置i-1-dp[i-1]是'('：
         • 则dp[i] = dp[i-1] +2
         • 如果i-2-dp[i-1]之前位置有有效括号长度，那么在以上基础上再加dp[i-2-dp[i-1]]
   • 计算顺序
     • 从前到后。遍历字符串，O(N)时间。
     • 每次计算完DP[i]，更新max(DP[i])。
     • 遍历完毕，返回结果。
4. 复杂度分析
   • 定义数组DP，O(N)空间。
   • 遍历字符串一次，O(N)时间。
5. 实现

   class Solution {
   public:
       int longestValidParentheses(string s) {
           vector<int>dp(s.size(), 0);
           int i, res=0;
           for(i=1; i<s.size(); i++){
               if(s[i]=='('){
                   dp[i]=0;
               }
               if(s[i]==')'){                
                   if(s[i-1]=='(' ){                                        
                       if(i-2 >= 0)
                           dp[i] = dp[i-2]+2;
                       else
                           dp[i] = 2;      // 应对测试用例"()"
                   }
                   // 应对测试用例"())"，控制边界i-1-dp[i-1]>=0
                   if(s[i-1]==')' && s[i-dp[i-1]]=='(' && i-1-dp[i-1]>=0 && s[i-1-dp[i-1]]=='('){
                       if(i-2-dp[i-1] >= 0)
                           dp[i] = dp[i-1] +2 + dp[i-2-dp[i-1]];
                       else
                           dp[i] = dp[i-1] +2;
                   }
               }
               res = max(dp[i], res);
           }
                   
           return res;
       }
   };
   

6. 参考