问题描述：
构造一个串，使得它包含所有的给定DNA序列，并且要求长度最短。
采用dfs策略，对于每个串定义1个指针，当全部指针为串尾时判断构造的长度，由于状态空间过大，但是又存在冗余搜索，可以用迭代加深将状态减少。最长待构造长度 + 当前长度 < 迭代的最大深度则直接return，大大减少了状态数。
代码如下：
#include <iostream>
using namespace std;
struct point 
{
int poi[8];
}temp;
char map[9][7];
int len[9];
int Min;
char DNA[] = {'A', 'C', 'G', 'T'};
int n;
int dfs(point tp, int sum, int depth) {
int i, j;
point temp;
if(sum > depth)
return 0;
for(i = 0; i < n; i++) {
if( len[i] - tp.poi[i] + sum > depth)
return 0;
}
for(i = 0; i < n; i++) {
if(map[i][ tp.poi[i] ])
break;
}
if(i == n) {
return 1;
}
int flag;
for(i = 0; i < 4; i++) {
flag = 0;
for(j = 0; j < n; j++) {
if(map[j][ tp.poi[j] ] == DNA[i]) {
flag = 1;
temp.poi[j] = tp.poi[j] + 1;
}else
temp.poi[j] = tp.poi[j];
}
if(flag)
if ( dfs(temp, sum + 1, depth) )
return 1;
}
return 0;
}
int main() {
int t, i;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%s", map[i]);
len[i] = strlen(map[i]);
}
for(i = 0; i < n; i++) {
temp.poi[i] = 0;
}
for(i = 1; ; i++) {
if( dfs(temp, 0, i) )
break;
}
printf("%d\n", i);
}
return 0;
}