最小括号序列，类似编辑距离

参考大佬的代码，整理一下思路。

本题有点类似编辑距离的动态规划，我们可以定义一个二维dp[][] ,dp[i][j] 表示 s字符串的前i个字符通过删除()操作，能否匹配t字符的前j个字符

操作的主体是s字符串，那么当前dp[i][j] 的有两种状态的转移：

s[i]==t[j] 不用删除当前的s[i] dp[i][j] |= dp[i-1][j-1]
s[i]==‘)’ 那么删除s[i]结尾的“）”的最小合法字符串序列假设到k dp[i][j] |=dp[k][j];
因为只有左括号和有括号两种符号，所以s[i] t[i] 只有相等或者不相等

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    string t;
    cin>>s>>t;
    int slen=s.size();
    int tlen=t.size();
    bool dp[slen+1][tlen+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=true;
    for(int i=1;i<=slen;i++){
        for(int j=1;j<=tlen;j++){
            if(s[i-1]==t[j-1]) dp[i][j]|=dp[i-1][j-1];
            if(s[i-1]==')'){
                int k=i-1;
                int cnt=1;
                while(cnt>0){
                    if(s[k-1]==')') cnt++;
                    else cnt--;
                    k--;
                }
                dp[i][j]|=dp[k][j];
            }
            
        }
    }
    if(dp[slen][tlen]) cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
}