自己对深搜理解的太垃圾了 (水了一天 )

深搜解决联通

1112. 迷宫

1113. 红与黑

4004. 传送阵

深搜解决连通性的问题

和普通的联通问题一样 bfs也可以解决

深搜搜索顺序

1116. 马走日

这搜索测试数据费时好好好好… 高啊

深搜维护信息分析

深搜维护走到的节点 以及走的步数 步数 == 棋盘数 方案数 ++

1117. 单词接龙

深搜维护信息分析

当前的单词string序列 以及目前走到的位置
需要回溯

1118. 分成互质组

深搜维护信息分析

深搜维护信息 是 组的id 组内第几个数 访问到数组的第几个数 组内从第几个数开始搜索
过程 对于数组内的某个数

• 如果能够满足check 且没被访问过 那么就将该数字加入到当前组内

• 不满足check 那么开辟新的数组 将组内维护信息置0

排列数字

深搜维护信息分析

深搜维护的一个值是我们搜索的位置
做完深搜需要回溯

扩展题 体操队形

题目分析 对每个全排列序列进行判断

牛牛嚯可乐

深搜维护信息分析

深搜维护的两个值是 分别为当前搜索到的位置 以及当前进行交换的次数
做完深搜需要回溯

重新排序得到 2 的幂

深搜维护信息分析

深搜维护的三个值 分别为原字符串 当前搜索到的位置 以及当前凑出来的整数

最大化一张图中的路径价值

深搜维护信息分析 学一手力扣建图

四个值 分别为枚举到哪个节点 花费 价值 最大时间

判断 花费大于mx 返回 
     回到0节点 更新最大值
     点未被访问 将价值加入即可

488. 祖玛游戏

深搜维护信息分析 学一手substr

2个值 一个是字符串 一个是用了多少球

397. 整数替换

做法挺多的 选择深搜 是因为自己深搜比较差

深搜解决树的问题

2049. 统计最高分的节点数目

深搜维护信息

深搜维护的是每个节点
这道题我们计算的是每个节点儿子节点的贡献 以及除去这个节点和它的子节点其他部分的贡献
并用map记录出现的最大值的次数

简单深搜的模板 (可能不对 希望指正)

void dfs(int u, ....) // u表示当前搜索到的位置 这个应该是必须的
{
    if (满足某个条件) 计算结果 return ;

    枚举所有子集
    {
        if (被访问过 || 满足某些剪枝条件 || ....) continue;
        标记
        dfs(); // 更改状态
        回溯
    }
}