判定性动态规划

题目描述
给你一个合法的括号序列s和t，能否在s中删除若干对括号(或者不删除括号)，使之变成序列t。

题目描述

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

输出描述

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

示例一
输入

(())
()

输出

Possible

示例二
输入

(()()())
((()))

输出

Impossible

示例三
输入

((())((())())())
(()(())())

输出

Possible

解题思路，区间dp版的判定性dp，第一次做哈，dp[i][j][k]代表s中前i个和t中前j个删去k个（删去左括号数量减去右括号数量）两个串是否匹配的集合，因为只能删左右配对的括号，最后求得就是dp[n][m][0]是否配对

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=110;
int dp[N][N][N];
int main()
{
	char s1[N],s2[N];
	scanf("%s",s1+1);
	scanf("%s",s2+1);
//	cout<<n<<' '<<m<<endl;
	int n=strlen(s1+1);
	int m=strlen(s2+1);
	//cout<<n<<' '<<m<<endl;
	dp[0][0][0]=1;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	for(int k=0;k<n/2;k++)//为什么是n/2呢因为左括号最多有n/2个，每个串都是合法的
	{
		if(dp[i][j][k])
		{
		if(!k&&s1[i+1]==s2[j+1])		//为什么!k呢，k>0时例如s1:()((s2()( dp[3][2][1]=true  
		//		dp[4][3][1]就不是有效的了，要连续删掉2个‘(’
		dp[i+1][j+1][k]=1;
		if(s1[i+1]=='(')
		dp[i+1][j][k+1]=1;
		if(s1[i+1]==')'&&k>0)
		dp[i+1][j][k-1]=1;
		
		}
	}
	if(dp[n][m][0])
	cout<<"Possible"<<endl;
	else
	cout<<"Impossible"<<endl;
    return 0;
}