删括号（DP）

链接：https://ac.nowcoder.com/acm/problem/21303
来源：牛客网

题目描述

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

输入描述:

第一行输入一个字符串s (2 ≤ |s| ≤ 100)
第二行输入一个字符串t (2 ≤ |t| ≤ 100 )

输出描述:

如果可以输出"Possible"否则输出"Impossible"

具体思路

dp[i][j][k] 表示第一个字符串的前i个和第二个字符串的前j个在可以删除若干个合法的‘（）’前提下，需要多删除多少个'('才能使得第一个字符串的前i个和第二个字符串的前j个相匹配。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 # define ll_inf (1ll<<60)
 6 const int maxn = 3e5+100;
 7 char str1[maxn],str2[maxn];
 8 int dp[100+10][100+10][100+10];
 9 int main(){
10 // 东邪西毒
11 scanf("%s",str1+1);
12 scanf("%s",str2+1);
13 dp[0][0][0]=1;
14 int len1=strlen(str1+1),len2=strlen(str2+1);
15 for(int i=0;i<len1;i++){
16 for(int j=0;j<=len2;j++){
17 for(int k=0;k<=len1;k++){
18 if(!dp[i][j][k])continue;
19 if(!k&&str1[i+1]==str2[j+1])dp[i+1][j+1][k]=1;
20 if(str1[i+1]=='(')dp[i+1][j][k+1]=1;
21 else if(k&&str1[i+1]==')')dp[i+1][j][k-1]=1;
22 }
23 }
24 }
25 if(dp[len1][len2][0])printf("Possible
");
26 else printf("Impossible
");
27 return 0;
28 }