牛客网 删括号 (线性dp)

题目

给你一个合法的括号序列s1，每次你可以删除一个"()" 你可以删除0个或者多个"()" 求能否删成另一个括号序列s2

|s1|,|s2|<=100

思路来源

https://blog.nowcoder.net/n/5ab7d33ec2484c50839f2a78b0b4a9ef?f=comment

https://www.bbsmax.com/A/MyJxYbNe5n/

题解

括号序列问题，总要开一维代表当前左括号数

dp[i][j][k]:代表到s的第i个字母t的第j个字母，且多删了k个左括号后，是否匹配

删的左右括号必相邻，即已经开始删左括号(k>0)之后，即使匹配也要删

如果当前是左括号，当前括号的右括号会在与删的左括号匹配的右括号前，所以必删

如果当前右括号，不删的话，会导致隔右括号，所以也必删

所以判完不删的充要条件之后，判断删(还是删)

代码

#include <bits/stdc++.h> using namespace std; const int N=110; char s[N],t[N]; bool dp[N][N][N]; int len1,len2; int main() { scanf("%s%s",s,t); len1=strlen(s),len2=strlen(t); dp[0][0][0]=1; for(int i=0;i<len1;++i) { for(int j=0;j<len2;++j) { for(int k=0;k<=len1/2;++k) { if(!dp[i][j][k])continue; //不删的充要条件 if(k==0&&s[i]==t[j])dp[i+1][j+1][k]=1; //上述二者不满其一 表示这位必删 if(s[i]=='(')dp[i+1][j][k+1]=1; else if(k)dp[i+1][j][k-1]=1; } } } puts(dp[len1][len2][0]?"Possible":"Impossible"); return 0; }