HDU - 1501 zipper (memory deep search)

Portal
The question ： give 3 A string a,b,c, ask c Yes No a,b Results after interleaving , That is to say a,b Without changing the character order of ,a,b The length of the string is less than 200
analysis ： If you search directly and deeply , Complexity is 2^200, So we need to use memorization , Space also relieves time , Mark the past situation . Record in the search a,b,c length ,c The length of is equal to ab Sum of length , therefore book[a][b] Represents the same situation , Mark the next time you get to this point return;
AC Code ：

#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
int l1,l2,l3;
char a[210],b[210],c[420];
int book[210][210];
int flag;
void dfs(int t1,int t2,int t3)
{
    
	if(t3==l3)
	{
    
		flag=1;
		return;
	}
	if(book[t1][t2])
	return;
	book[t1][t2]=1;
	if(a[t1]==c[t3])
	dfs(t1+1,t2,t3+1);
	if(b[t2]==c[t3])
	dfs(t1,t2+1,t3+1);
}
int main() 
{
    
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
    
		memset(book,0,sizeof(book));
		flag=0;
		scanf("%s",a);
		scanf("%s",b);
		scanf("%s",c);
		l1=strlen(a);
		l2=strlen(b);
		l3=strlen(c);
		dfs(0,0,0);
		if(flag==1)
		printf("Data set %d: yes\n",i);
		else printf("Data set %d: no\n",i);
	}
}