DFS递归复习总结

递归DFS上午一、连续子段切分问题二、自然数拆分三、放苹果四、复原IP地址五、回文质数六、吃奶酪下午一、DFS 难点该不该回溯二、Lake Counting 数池塘三、迷宫四、填涂颜色五、Cow Travelling S六、回家七、棋盘上午一、连续子段切分问题给定一条长度为n nn的连续序列数组或字符串在序列内部选择若干个切分点将其划分为若干个不重叠、非空的连续区间。二、自然数拆分问题将n nn拆分成若干个小于n nn的自然数之和按字典序输出所有方案。思路为保证不重复且按字典序输出拆分出的数字必须非递减即后一个加数不能小于前一个加数。参数需要维护三个变量——剩余待拆分的数值、上一个拆分出的数字保证非递减、当前正在算第几个加数。边界当剩余数值为0 00时说明拆分完毕此时要排除掉只有一个加数的情况即n nn等于自身这种不合法拆分只有加数个数大于等于2 22时才输出。枚举范围从上一个加数开始枚举到剩余数值这样既保证了非递减排列又保证当前数不会超过剩余总和。评价我以前真的不会。三、放苹果问题M MM个相同苹果放入N NN个相同盘子允许空盘求方案数。参数以当前待放入的苹果数量和当前可用盘子数量作为状态。边界苹果数为0 00或盘子数为1 11时只有1 11种放法苹果数为负或盘子数小于等于0 00时属于非法状态返回0 00。分类讨论当盘子数多于苹果数时必然有若干盘子空着此时等价于把苹果放到与苹果数量相同的盘子里当苹果数不少于盘子数时分为两种互斥情况至少有一个盘子空着或者每个盘子都至少放一个苹果。后者可以理解为先在每个盘子各放一个保底剩余的苹果再任意分配。评价递归的参数有点容易写错。四、复原IP地址问题将数字字符串切分为4 44段每段数值在0 00到255 255255之间不能有前导0 00按字典序输出所有可能结果。参数需要维护当前切分的起始位置和已经切分完成的段数。递归边界已经切出4 44段且字符串刚好用完说明找到一个有效划分保存结果已经切出4 44段但字符串还有剩余直接滚。剪枝根据剩余字符数和剩余段数判断是否可能完成。剩余字符太少无法组成足够的段剩余字符太多超出每段长度上限两种情况都直接滚蛋。评价其实可以枚举当前的数字长度来DFS。五、回文质数问题求给定区间内所有既是质数又是回文数的整数按从小到大顺序输出。思路构造回文数非常稀疏不逐个数去检验它是不是回文数而是用搜索直接构造出回文数。回文数具有回文性由前一半数位决定偶数位全灭定律任何一个具有偶数位长度的回文数其奇数位数字之和一定等于偶数位数字之和能被 11 整除是合数。唯一的偶数位回文质数只有 11 本身只需构造奇数位除特判 11 外只需构造总长度为奇数位的回文数。提示不能直接在构造前特判11因为前面还有个2、5、7。评价感觉不是很难主要就是想到要先构造回文数再判断质数还有这个坑。六、吃奶酪问题n 块奶酪分散在二维平面上老鼠从原点出发要吃掉所有奶酪求最少需要跑多远。解法状态定义用二进制数表示奶酪被吃掉的集合状态用当前最后到达的奶酪编号作为位置信息记录达到该状态的最短距离状态转移枚举下一个要去但还未去的点尝试移动到该点最小距离等于所有尝试中当前距离加上后续最小距离的最小值评价一道不难的状压主要是得想到要用当前最后到达的奶酪编号作为位置信息。下午一、DFS 难点该不该回溯DFS 的主要难点不在于递归本身而在于是否需要编写回溯。该回溯时漏写会出错不该回溯时滥写同样会出错。维度染色连通块路径方案搜索 / 轨迹回溯目标统计连通块个数、面积、岛屿边界统计路径条数、输出最短路径轨迹、求解特定步数解标记标记后永不还原进递归打标递归返回后必须清空空间单个节点全过程只被访问一次单个节点在不同走法/分支中可被复用复杂度每个格子常数次进出最坏指数级必须依赖强剪枝坑统计岛屿面积时写了恢复现场直接爆搜超时找迷宫所有路径时没清标记导致漏解二、Lake Counting 数池塘问题给定N × M N×MN×M网格格子为W或.。八连通的水格属于同一池塘求独立池塘总数。解题思路统计连通块总数不需要枚举路径因此每个水格只需被访问一次。遍历全图发现未访问的W则池塘计数加一从该格启动DFS向八个方向扩散途中遇到的所有连通W直接消去原地改为.搜索返回时不撤销修改保证每格只进出一次。评价不要双重for枚举点如果前面没有W就。三、迷宫问题N × M N×MN×M方格迷宫给定起点、终点和T TT个障碍物每次只能上下左右移动一格同一条路径不能重复经过同一格子求不同可行路径总数。解题思路路径方案搜索要求枚举所有走法同一个格子虽然在一条路径中不能复用但在不同路径中可以被再次经过。因此必须回溯递归进入下一层前标记访问该子树搜索完毕返回后恢复标记。评价那这很板了。四、填涂颜色问题n × n n×nn×n矩阵1 11代表闭合圈围墙0 00代表空地闭合圈内不含其他圈。将所有被1 11完全闭合包围的0 00填涂为2 22未被包围的0 00保持不变。解题思路正难则反不好去模拟于是我们可以先把外面的0 00变掉剩下的0 00就是里面的0 00坑点不能只从左上角开始万一左上角是1 11你不炸了。评价主要是要想到zl则反。五、Cow Travelling S问题N × M N×MN×M网格部分格子有障碍奶牛从起点出发必须在恰好第T TT秒到达终点每秒只能向相邻空地移动一步同一个格子可以重复经过求恰好T TT秒到达终点的总路线方案数。解题思路节点可重复走无需v i s visvis数组直接以步数等于T TT终止状态树分支为4 T 4^T4T次方暴搜超时剪枝一可行性剪枝当前点到终点的理论最短距离。如果剩余可用步数小于该距离不可能按时到达立即滚剪枝二奇偶剪枝如果剩下的步数与终点的距离不同那么一定不可能按时到达滚掉。评价得想到减枝其中剪枝二要难想一点其实都不难想。六、回家问题n × m n×mn×m地图2 22为起点3 33为家0 00为障碍1 11为空地4 44为有鼠标的空地。初始生命值为6 66每走一步生命值减一归零立即死亡吃到鼠标时生命值立即回满至6 66。求到达终点所需最少步数无法到达输出− 1 -1−1。解题思路坑点普通布尔数组 vis[x][y] 会导致漏解得加一个走到这里是还有多少生命评价就是稍微难模拟一点也不难。七、棋盘问题没时间了直接上图片解题思路坑点不能重复施法当法师大王。评价注意标记建议分块调试思路不难。