链接：https://ac.nowcoder.com/acm/problem/21303 来源：牛客网 题号：NC21303 时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒 空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M 64bit IO Format: %lld 题目描述 给你一个合法的括号序列s1，每次你可以删除一个"()" 你可以删除0个或者多个"()" 求能否删成另一个括号序列s2 输入描述: 第一行输入一个字符串s (2 ≤ |s| ≤ 100) 第二行输入一个字符串t (2 ≤ |t| ≤ 100 ) 输出描述: 如果可以输出"Possible" 否则输出"Impossible"

比较有意思的题目，如果能想明白括号是怎么删的就不难解决，用动态规划是因为每步走完后会产生新状态，一种情况可能有好几种状态， 代码2里面的k就是记录状态数的

每一步可能遇到哪些情况？

1.匹配，"("与"("或者")"与")"

2.不匹配，"("与")""或者")"与"("

不匹配就要删括号，难点来了，当时思考")"前面全是匹配过的"("怎么办，比如()(())变成(()),直接回退是不行的，遇到"(())(()()())"删成"(()()())"这种情况会直接乱套，

怎么办？细想会发现，如果括号序列1能合法删成括号序列2，括号序列2中如果有x个连续的'(',那么序列1中也一定要有x个连续的'(',很多题解说不会出现要删的'('数量一定是大于等于')'就是这个原因.(假设序列2有三个'('连续，那么就在序列1三个'('连续的位置开始匹配)。

现在再来看"()(())"删成"(())"这种情况，"()"完全是不需要匹配的，那么怎么用代码实现呢？处理'('与'('时不止是拓展"匹配成功，往后看",还要考虑"放弃匹配往后看"。

怎么保证删的括号一定合法？

在串1要多删字符才能到串2时，只选择删，不选择匹配，这样删的括号一定是匹配的，而且可以让序列1从连续左括号数相同的位置开始与序列2匹配。 代码1

dp[i][j][k]表示括号串1的前i位与括号串2的前j位在1多删除k个左括号后是否可以匹配

#include<vector>
#include<string>

using namespace std;
void DP(const string& s, const string& evil)
{
	int s_len = s.length();
	int evil_len = evil.length();
	vector<vector<vector<bool>>>dp(s_len + 1, vector<vector<bool>>(evil_len+1,vector<bool>(s_len/2+1,false)));
	dp[0][0][0] = true;//两串前0个字符可以在不多删左括号时匹配
	for (int j = 0; j <= evil_len; j++)
	{
		for (int i = 0; i <= s_len; i++)
		{
			for (int k = 0; k <dp[i][j].size(); k++)
			{
				if (!dp[i][j][k])continue;//过滤掉未出现的情况
				if (k==0&&s[i] == evil[j])
				{
					if(i+1<=s_len&&j+1<=evil_len)
					dp[i+1][j+1][k] = true;//考虑匹配
					if (i + 1 <= s_len && s[i] == '(')
						dp[i + 1][j][k + 1] = true;//考虑不匹配，待删左括号数加一
				}
				//不匹配或者有待删左括号
				else if (i + 1 <= s_len && s[i] == '(')
				{
						dp[i+1][j][k + 1] = true;//待删左括号加一
				}
				else if (s[i] == ')')
				{
					if (i + 1 <= s_len && k - 1 >= 0)
						dp[i+1][j][k - 1] = true;//待删左括号减一
				}
			}
		}
		
	}
	//debug
	/*for (int i = 0; i <= s_len; i++)
	{
		for (int j = 0; j <= evil_len; j++)
		{
			for (int k = 0; k <= evil_len / 2; k++)
			{
				cout << "dp[" << i << "][" << j << "][" << k << "]:" << dp[i][j][k] << endl;
			}
		}
	}*/
	if (dp[s_len][evil_len][0])cout << "Possible";
	else cout << "Impossible";
}
int main(void)
{
	string s, evil;
	cin >> s >> evil;
	DP(s, evil);
	return 0;
}

代码2

代码1考虑情况是设dp为true，过滤掉不存在的情况，这个代码是直接开情况

#include<string>
#include<vector>

using namespace std;


void DP(const string&s,const string&evil)
{
	int s_len = s.length();
	int evil_len = evil.length();
	vector<vector<vector<int>>>dp(s_len+1, vector<vector<int>>(evil_len+1,vector<int>()));//s前i个字符，evil前j个字符，有k种情况对应待删左括号数
	dp[0][0].push_back(0);
	for (int j = 0; j <= evil_len; j++)
	{
		for (int i = 0; i <= s_len; i++)
		{
			for (int k = 0; k < dp[i][j].size(); k++)
			{
				if (s[i] == evil[j]&&dp[i][j][k]==0)
				{
					if(i+1<=s_len&&j+1<=evil_len)
					dp[i + 1][j + 1].push_back(0);
					if (i + 1 <= s_len && s[i] == '(')
						dp[i + 1][j].push_back(1);
				}
				else if (i + 1 <= s_len && s[i] == '(')
				{
					dp[i + 1][j].push_back(dp[i][j][k] + 1);
				}
				else if (i + 1 <= s_len && s[i] == ')')
				{
					if(dp[i][j][k]>0)
					dp[i + 1][j].push_back(dp[i][j][k]-1);
				}
			}
		}
	}
	//debug
	/*for (int i = 0; i <= s_len; i++)
	{
		for (int j = 0; j <= evil_len; j++)
		{
			for (int k = 0; k < dp[i][j].size(); k++)
			{
				cout << "dp[" << i << "][" << j << "][" << k << "]:" << dp[i][j][k] << endl;
			}
		}
	}*/
	bool ans = false;
	for (int k = 0; k < dp[s_len][evil_len].size(); k++)
	{
		if (dp[s_len][evil_len][k] == 0)ans = true;
	}
	if (ans)cout << "Possible";
	else cout << "Impossible";
}
int main(void)
{
	string s, evil;
	cin >> s >> evil;
	DP(s, evil);
	return 0;
}

代码2虽然AC了，但是内存比代码1多了将近一倍，实际上绝对不止一倍，如果字符串更长的话这个代码内存增长是指数级的，因为这个代码会重复记录效果相同的情况，把debug注释去掉就明白了，i，j相同，有的k对应的是相同的，如果统计dp[s_len][evil_len][k]里面值为0的dp的个数，得到的应该是把s合法删成evil的方案数(个人理解，未验证哈)，要针对这题优化的话，可以考虑用map去重

这题的dp就是不断增加合法新情况，在新情况的条件上再加合法新情况，是不是对动态规划“把问题化成重叠子问题”有新理解了呢