左括号(和右括号)组成,返回最长有效括号子串的长度,动态规划
程序员文章站
2022-03-24 20:42:04
...
已知一个字符串都是由左括号(和右括号)组成,返回最长有效括号子串的长度。
题目如上,
利用动态规划,设定dp[i]状态为 第 i个位置的连续最长子串的长度。所以
当出现“(”时,由于自己本身不能构成左右括号,所以 dp[i] = 0
当出现“)”时,要对前面的有效组成进行判断,即先对dp[i-1]进行判断,表示在自己匹配之前,看看其之前是否已经有满足匹配的了,如果有,那么就查看dp[i-1] 个之前的位置是不是有 匹配的“(”,如果有那么当前就是dp[i] = dp[i-1] +2. 并且还需要考虑到之前的 i-dp[i-1] -1-1 的位置是否有匹配的,因为可能之前有匹配成功的,但是在某一时刻是断开的,没有考虑进来,所以需要将其加入其中。示意图如下所示:
代码如下
#include <iostream>
#include <stdio.h>
#include<string>
using namespace std;
//用于存放第 i个位置为止 与之匹配的括号数量
int dp[1000]={0};
int main() {
string arr;
cin>> arr;
for(int i=0;i<arr.length();i++){
//如果是左括号,那么从这个位置开始,匹配数为0
if(arr[i] == '('){
dp[i] = 0;
}else if(arr[i] == ')'){
//减去当前已经匹配的数量
int index = i-dp[i-1]-1;
if( index>=0 && arr[index] == '('){
//如果也匹配上,则+2
dp[i] = dp[i-1]+2;
if (i-dp[i-1]-2>=0){
//还要检查之前是否有匹配的数量
dp[i]+=dp[i-dp[i-1]-2];
}
}
}else{
cout<<0<<endl;
break;
}
}
int max_ = dp[0];
for (int i=0;i<arr.length();i++){
if(max_<dp[i]) max_ = dp[i];
}
cout<<max_<<endl;
return 0;
}
上一篇: 动态规划-面试题49. 丑数