题目链接

题意：

 题目是中文的，不用我再进行赘述，但是这里要注意：删除的'('和')'必须是相邻的

思路：

 说实话，要不是这个题被分到动态规划的题单里面，我是绝对不信这是一个dp题
首先,我们先定义好dp变量,
dp[i,j,k]表示1串前i在删除的'('数量-删去的')'为k时是否与2串的前j项相等，可以采用bool类型的数组
且初值是dp[0][0][0] = true

递推公式如下:

当dp[i,j,k] = true && k == 0时 说明1，2两串上一次是匹配的，而且删除的括号也是成对的

  • 1如果str1[i + 1] == str2[j + 1] && k == 0就有 dp[i + 1,j + 1,k] = true
  • 2如果str1[i + 1] == '(' 或者str1[i + 1] == ')'我们都可以考虑是否删掉它
    即对应1串中的每一个字符，我们都有两种考虑 保留或者删除,对于上一步的dp[i,j,k] = true&&k == 0如果当前i j对应的字符可以匹配，那么我们就有两种选择，保留或者删除
    (1)如果保留，那么就有dp[i + 1,j + 1,k] = true
    (2)如果删除，就要看当前字符是'('或')' 与其对应的状态转移分别为
    dp[i + 1,j,k + 1] = true ,dp[i + 1,j,k -1] = true
    如果不满足str1[i + 1] == str2[j + 1] && k == 0，那么我们只能进行删除操作，因为我们一次要删除的是一对相邻的括号，所以必须是k 为0 的时候才能进行与串2的匹配，而删除操作则是找到在i某种合法删除的情况下进行匹配

总的来说，这个过程也反映了动态规划其实在某种程度上也是一种暴力的记忆化搜索

代码

#include <bits/stdc++.h>

#define __int128 LL

using namespace std;

typedef long long ll;

const int mod = 1e9;
const int maxn = 1e3 + 5;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);

string str1,str2;
bool dp[105][105][55];
//dp[i][j][k]表示1串前i在删除的'('数量-删去的')'为k时是否与2串的前j项相等

void Solve(const string &str1,const string &str2)
{
    memset(dp,false,sizeof dp);
    dp[0][0][0] = true;
    int len1 = str1.size(),len2 = str2.size();
    for(int i = 0; i < len1; i++){
        for(int j = 0; j < len2; j++){
            for(int k = 0; k <= len1 / 2; k++){//由于所有字符串合法,所以肯定是两种符号各占一半
                //这种情况下前i和前j个相同
                if(dp[i][j][k]){
                    //如果删除的"("和")"成对
                    if(!k&&str1[i + 1] == str2[j + 1]) dp[i + 1][j + 1][k] = true;//可以保留
                    //对于多出来一个'('如果把这个字符删掉,就可以匹配,而且
                    //k数量要多1,因为比上一次多删除了一个'('
                    if(str1[i + 1] == '(') dp[i + 1][j][k + 1] = true;//如果第一个if成立，这就是第二种状态，如果不成立
                    //就是只有一种状态，试想，如果这个字符不能匹配，肯定是要删除的
                    //或者k不为0就说明必须要继续删除字符直到k为0的状态再判断
                    //我们已知再dp[i][j][k]为真,所以当第str1[i + 1]= ')'时
                    //我们把这个字符删除也是可以使dp[i + 1][j][k - 1]成立
                    //并且由于删除了一个')'却没有删除'('所以k的值要-1
                    else if(k) dp[i + 1][j][k - 1] = true;
                }
            }   
        }
    }
    if(dp[len1] [len2][0]) cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
}

int main()
{
    cin>>str1>>str2;
    Solve(str1,str2);
    return 0;
}