题解 | #删括号#

很难 至少是我这个水平来看 贴一篇题解 https://blog.csdn.net/weixin_52829980/article/details/115037993 我只能勉强理解 第三层嵌套循环可以理解为枚举删除k个左括号的情况。

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[105],t[105];
    scanf("%s%s",s+1,t+1);
    int len1=strlen(s+1);
    int len2=strlen(t+1);
    bool dp[105][105][55];
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=true;
    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])
                {
                if(k==0&&s[i+1]==t[j+1]) dp[i+1][j+1][0]=true;
                if(s[i+1]=='(') dp[i+1][j][k+1]=true;
                else if(k) dp[i+1][j][k-1]=true;
                }
            }
        }
   }
   if(dp[len1][len2][0])   cout << "Possible"<<endl;
   else cout << "Impossible\n";
   return 0;
}