图---DFS剪枝

论坛 期权论坛 编程之家     
选择匿名的用户   2021-5-30 15:51   11   0

DFS剪枝即对DFS进行适当优化,满足条件则退出递归,不需要遍历完所有情况。

例如下面出自POJ的题目:

TCGG

GCAG

CCGC

GATC

ATCG

这五个串是一个原串的子串,求最小原串的长度?例如答案11:CCGCAGATCGG

步骤:

1. 计算任意两个串合并后增加的长度 Mer[5][5]

2. 对每个子串进行DFS:

a 达到N串退出

b 当前增加长度已大于之前计算出的长度,则优先退出

c 没访问过的DFS,注意visited[k]=1后重新置回visited[k]=0

note:

1. 复习递归:

a 分析子问题

b 写退出口

c 优化退出口

d visited 重置问题

2. 分析出问题的关健是两两merge

转载于:https://www.cnblogs.com/xfei-zhang/p/5086869.html

分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:3875789
帖子:775174
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP