2192:Zipper

#include <bits/stdc++.h>
using namespace std;
//0、状态是什么？怎么表示 
//1、分解成子问题 
//2、无后效性，一种状态A只与另一种状态B的值有关，与状态B的到达方式无关 
string s1,s2,s3;//用string 声明字符串就不用考虑字符串长度 
int len1,len2,len3;
int dp[205][205];// dp[i][j]为1或0表示s1前i个字符段与 s2前j个字符段 是否匹配成功，这就是状态 
int main(int argc, char** argv) {
	int t;
	cin>>t;
	for(int k=1;k<=t;k++){
		memset(dp,0,sizeof(dp));
		cin>>s1>>s2>>s3;
		len1=s1.size();//strlen（）是用于char a[100];这样声明数组的时候噢 
		len2=s2.size();
		len3=s3.size();
//试想，如果s1前i个字符段与 s2前j个字符段匹配成功，则s3[i+j]要么等于s1[i]
//，要么等于 s2[j],同理判断dp[i][j]应该判断 
	/*
		for(int i=0;i<=len1;i++){
			dp[i][0]=1;
		}
		for(int j=0;j<=len2;j++){
			dp[0][j]=1;
		}
	 
//一则，只要一个字符串为空，只有0个字符，一定匹配成功
//二则，判断 s1前i个字符段与 s2前j个字符段是否匹配成功时，要考虑dp[i-1][j-1]
//，如果是 s1或s2只有一个字符，判断s1[i]或s2[j]==s3[i+j]就够了 不需要讨论除去
//s1[i]和s2[j]之后的两段字符串匹配情况，因为其中一个串没有字符了，一定匹配 
		for(int i=1;i<=len1;i++){
			for(int j=1;j<=len2;j++){
//				if(s1[i]==s3[i+j]&&dp[i-1][j]==1)dp[i][j]=1; 
//				if(s2[j]==s3[i+j]&&dp[i][j-1]==1)dp[i][j]=1; 
			if(s1[i]==s3[i+j])dp[j + 1][k] = dp[j][k] || dp[j + 1][k]; 
			if(s2[j]==s3[i+j])dp[j][k + 1] = dp[j][k] || dp[j][k + 1]; 
				
			}
		} 
错了，并非只要s1，s2有一个为空就一定匹配，匹不匹配要看给的s3!!!!!哪！！！!!!!!
还有，动态规划递推总是想让数组存储下标从1开始，好让状态表示的意义与实际意义相同
但应该考虑考虑，状态里是否有这种0的情况，比如，长度为0的字符串与另一个字符串找公共子串
再比如此题， s1或s2只有0个字符，能否与另一个字符串匹配出s3 
		*/
//		递推总要初始化一些边界值 
			dp[0][0]=1;
			for(int i=0;i<=len1;i++){
			for(int j=0;j<=len2;j++){
		
		//由于数组下标从0开始，这里表示的含义要格外注意，s[i]表示的是s字符串中第i+1个字符
//而dp[i][j]则表示s1字符串中前i个字符与s2字符串中前j个字符是否匹配！！！
//这个二重循环是为了递推补充dp数组的数据，自然要按dp数组的下标来 此时就要注意
//s数组下标与dp数组下标的关系 

			if((i<len1&&s1[i]==s3[i+j])&&dp[i][j])dp[i+1][j]=1;
//也就是说s1字符串中前i个字符与s2字符串中前j个字符匹配并且s3中第i+j+1个数据是
//s1的第i+1个元素 
			if((j<len2&&s2[j]==s3[i+j])&&dp[i][j])dp[i][j+1]=1;
			}
		}
		if(dp[len1][len2]==1)printf("Data set %d: yes\n",k);
		else printf("Data set %d: no\n",k);
	} 
	return 0;
}

原来提交时的代码中有如此琐碎长篇的注释，还会出现runtime error~~
错误思想：
//一则，只要一个字符串为空，只有0个字符，一定匹配成功
//二则，判断 s1前i个字符段与 s2前j个字符段是否匹配成功时，要考虑dp[i-1][j-1]
//，如果是 s1或s2只有一个字符，判断s1[i]或s2[j]==s3[i+j]就够了 不需要讨论除去
//s1[i]和s2[j]之后的两段字符串匹配情况，因为其中一个串没有字符了，一定匹配

		for(int i=1;i<=len1;i++){
			for(int j=1;j<=len2;j++){
//				if(s1[i]==s3[i+j]&&dp[i-1][j]==1)dp[i][j]=1; 
//				if(s2[j]==s3[i+j]&&dp[i][j-1]==1)dp[i][j]=1; 
			if(s1[i]==s3[i+j])dp[j + 1][k] = dp[j][k] || dp[j + 1][k]; 
			if(s2[j]==s3[i+j])dp[j][k + 1] = dp[j][k] || dp[j][k + 1]; 
				
			}
		} 

×××××××××××××××
Reason：错了，并非只要s1，s2有一个为空就一定匹配，匹不匹配要看给的s3!!!哪！！！!!!
还有，动态规划递推总是想让数组存储下标从1开始，好让状态表示的意义与实际意义相同
但应该考虑考虑，状态里是否有这种0的情况，比如，长度为0的字符串与另一个字符串找公共子串
再比如此题， s1或s2只有0个字符，能否与另一个字符串匹配出s3

由于数组下标从0开始，这里表示的含义要格外注意，s[i]表示的是s字符串中第i+1个字符
//而dp[i][j]则表示s1字符串中前i个字符与s2字符串中前j个字符是否匹配！！！
//这个二重循环是为了递推补充dp数组的数据，自然要按dp数组的下标来 此时就要注意
//s数组下标与dp数组下标的关系

		if((i<len1&&s1[i]==s3[i+j])&&dp[i][j])dp[i+1][j]=1;

//也就是说s1字符串中前i个字符与s2字符串中前j个字符匹配并且s3中第i+j+1个数据是
//s1的第i+1个元素

递推总要初始化一些边界值 ,再依据已知的值去递推其他的数据呀！
想想数字三角形的最下边一行

思想还是比较混乱，但对下一道题还是那么的跃跃欲试！

最后附上这道题的DFS解法，就当是提前了解以下DFS深度优先搜索算法

#include <bits/stdc++.h>
using namespace std; 
string s1,s2,s3;//用string 声明字符串就不用考虑字符串长度 
int len1,len2,len3;
int flag;
void DFS(int i,int j,int k){
	if(k==len3){
		flag=1;
		return ;
	}
	if(s1[i]==s3[k])DFS(i+1,j,k+1);
	 if(s2[j]==s3[k])DFS(i,j+1,k+1);
	 return ;
}
int main(int argc, char** argv){
	int t;
	cin>>t;
	for(int k=1;k<=t;k++){
		flag=0;
		cin>>s1>>s2>>s3;
		len1=s1.size();//strlen（）是用于char a[100];这样声明数组的时候噢 
		len2=s2.size();
		len3=s3.size();
		DFS(0,0,0);
		if(flag==1)printf("Data set %d: yes\n",k);
		else printf("Data set %d: no\n",k);
	} 
	return 0;
}

会超时
——用时间换空间
所以增加一个判断是否访问过的数组flag

#include <bits/stdc++.h>
using namespace std; 
string s1,s2,s3;//用string 声明字符串就不用考虑字符串长度 
int len1,len2,len3;
int fla;
int flag[205][205];
void DFS(int i,int j,int k){
	if(flag[i][j]==0)
{
		if(k==len3){
		fla=1;
		return ;
	}
	if(s1[i]==s3[k])DFS(i+1,j,k+1);
	 if(s2[j]==s3[k])DFS(i,j+1,k+1);
	 flag[i][j]=1;
}
	 return ;
}
int main(int argc, char** argv){
	int t;
	cin>>t;
	for(int k=1;k<=t;k++){
		fla=0;
		memset(flag,0,sizeof(flag));
		cin>>s1>>s2>>s3;
		len1=s1.size();//strlen（）是用于char a[100];这样声明数组的时候噢 
		len2=s2.size();
		len3=s3.size();
		DFS(0,0,0);
		if(fla==1)printf("Data set %d: yes\n",k);
		else printf("Data set %d: no\n",k);
	} 
	return 0;
}

时间换空间的原理我懂，但是没太想明白，为什么会重复判断
s1[i], s2[j]是否匹配呢？？？