AK F.*ing leetcode 流浪计划之DFS

LightningBilly · 2021 年6 月 5 日 10:37

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

广度优先搜索算法BFS（广搜）是图的一种遍历方式，类似于树的层次遍历。

深度优先搜索算法DFS(深搜)是图的一种遍历方式。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

由DFS衍生出来的相关应用算法比较多，主要可以分为图应用、回溯法（遍历所有解）、带剪枝的回溯法（求解最优解或判断是否有解）、记忆化搜索（动态规划递归版本实现）。

DFS和BFS也是一种暴力搜索的算法，通常情况下也很完备，对于整体状态的数量要事先估计。对于带剪枝的回溯算法要充分分析剪枝条件的正确性，以免剪掉一些可行解，导致答案不完备。

由于DFS是基于递归的一个过程，学习DFS算法对于理解递归过程非常有帮助，通过练习掌握递归的常规应用。

二、作用

图（树）应用

深度优先遍历结点
判断图中2点是否连通
查找图的连通块

回溯法应用，该算法大多是用于模拟求解。先把问题拆解成某一个基础操作，在每一层做一个基础操作，直到确定唯一解，然后再逐步回溯。

比如：

全排列生成，一开始有n个数字，从第1个位置到n位置，每个位置选择一个数字，直到数字选完产生一个排列，再继续回溯。
走迷宫，每次都选择一个方向走，直到走不动或离开迷宫，就是生成了一条路线，然后再回溯。
对一堆数字生成子集。对每个数字，进集合或者不进集合，当用完所有数字就形成一个子集，再回溯。
八皇后问题，每行选择一个可以放的位置，直到放完所有行，再回溯。

带剪枝的回溯法，该算法一般用于求解某个问题是否有解或问题的最优解。他与回溯法的区别就是递归的终止条件会更多（普通回溯法的终止条件就是元素都操作完了），使得递归次数大大减少。

比如

求解数组（都是非负数）中的某几个数字之和是否等于目标值，基本思想可以生成所有子集，然后判断子集之和是否等于目标值，可以增加终止条件：如果剩下的数字都加上也无法达到目标值就返回。

记忆化搜索求解动态规划问题

动态规划有2种实现方式，递推和递归求解。递推是自底向上，关键要找到这个底在哪里，有些动态规划问题不容易找到底，所以用递归求解更容易实现。递归求解会存在重复求解，需要引入一个map标记是否已求解过，故名记忆化搜索。

三、解题步骤

图遍历应用

解题步骤

定义数据

定义结点数据和孩子数据

具体操作

step 1 选择一个没有遍历过的点

step 2 判断该结点是否已经遍历，是则转6

Step 4 标记当前结点已遍历

step 5 遍历子结点

		1. 判断子结点是否合法
		2. 转step2

step 6 查看是否还有未遍历结点，有则转1，没有转7

step 7 结束

回溯法（剪枝）应用

适用条件：

整体递归层数不能太多，10多个可以接受。
总体状态数量要控制在百万级别，剪枝的话要看情况，可以扩大到千万甚至更高。

解题步骤

定义数据

定义每一层的状态
定义状态转移操作
定义基础结束条件
定义剪枝条件

具体操作

step 1 选择起状态

step 2 判断该状态是否结束，是则返回

Step 3 判断该状态是否剪枝，是则返回（非剪枝可以不要）

step 4 生成和遍历子状态

		1. 判断子状态是否合法
		2. 转step2

step 5 结束

记忆化搜索动态规划应用

适用条件：

所有动态规划问题

解题步骤

定义数据

定义状态
定义结束条件
定义转移方程

具体操作

step 1 选择起状态

step 2 判断该状态是否结束，是则返回结束值

Step 3 判断该状态是否计算过，是则返回

step 4 根据转移方程计算子状态

转到2
标记本状态计算完成，并保存计算结果

step 5 结束

四、代码框架

图遍历框架

// 图遍历框架
vis // 表示 某状态是否被访问过, 针对有环图的情况需要判断，无环图不用
func DFS(start State)  {
	if vis[start] {return}
	vis[start]<-true
	// 对start 进行一些操作
	visit(start)
	
	// 遍历子结点
	for child <- start.Children {
		DFS(child)
	}
}

回溯法（剪枝）框架

// 回溯法（剪枝）框架
func DFS(dep int, start State) {
	 // 判断当前状态的基本条件
	 if isEnd(start) {
	 		// 得到一个结果进行存储
      do sth ...
	 		return
	 }
	 
	 // 剪枝条件判断(非剪枝这步可以不要)
	 if isCut(start) {return}
	 
	 
	 // 进行下一层选择
	 for child<-start.Children {
	 		DFS(dep+1, child)
	 }
}

记忆化搜索框架

// 记忆化搜索框架
vis // 存储是否计算过
val // 计算结果值
func dp(start State)  {
	 // 判断当前是否结束条件
	 if isEnd(start) {return 结果 }
		
	 // 判断是否计算过
	 if vis[start] {val[start]}
	 vis[start]=true
	 	 
	 // 进行子状态转移
	 for child<-start.Children {
	 	val = dp(child)
	 	// 对val进行一些操作
	 }
	 
	 return val[start]
}

Dfs 应用很广，具体每种应该只能大致分成几个部分，没有固定的写法。具体需要做题来感受。

五、牛刀小试

练习1 图深度优先遍历应用省份数量

题目链接力扣

题目大意

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i\][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j

题目解析

题目中给出图是矩阵表示法，先把图转化成链表表示法。

按照题意，一个省就是图中的一个连通块。

可以通过DFS算法去查询一个连通块。

AC代码

func getLinks(isConnected [][]int) [][]int {
	links := make([][]int, len(isConnected))
	for i, row := range isConnected {
		for j, v := range row {
			if i == j { // 排除自己
				continue
			}

			if v == 0 {
				continue
			}
			links[i] = append(links[i], j)
		}
	}
	return links
}

func findCircleNum(isConnected [][]int) int {
	links := getLinks(isConnected)

	sum := 0
	vis := make(map[int]bool)
	
	var dfs func (int) 
	dfs = func (i int)  {
		if vis[i] { // 已经访问过了，直接返回
			return 
		}
		vis[i]=true
		
		for _, child :=range links[i] {
			dfs(child)
		}
	}
	
	for i:=0;i<len(isConnected) ;i++ {
		if vis[i] { // 访问过了
			continue
		}
		
		// 没访问过
		sum++
		dfs(i) // 把与i在同一省的城市都遍历
	}

	return sum
}
/*
[[1,1,0],[1,1,0],[0,0,1]]
[[1,0,0],[0,1,0],[0,0,1]]
[[1]]
*/

练习2 回溯法应用全排列

题目链接：力扣

题目大意

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

题目解析

可以通过回溯法解决。

按照朴素数学做法，以[1,2,3]为例

先选择第1位，1

再从剩下中选择第二位，形成[1，2]， [1，3]

再从剩下中选择第三位，形成[1, 2, 3], [1, 3, 2]

同理第1位选择2，最终产生出 [2，1，3]，[2，3，1]

第1位选择3省略。

根据以上模拟可以发现，

每次操作都是在某一位上选择一个没被用过的数字。

定义：

定义每一层的状态，当前第几位数字待选
定义状态转移操作，待选数字序号加1
定义基础结束条件，所有集合数字已经用完

AC代码

func permute(nums []int) [][]int {
	res := [][]int{}
	vis := make(map[int]bool) // 标记是否已经被选择
	var dfs func(int, []int) 
	dfs = func(i int, arr []int){
		if i==len(nums) { // 选完所有数字产生一组排列
			temp := make([]int, len(nums))
			copy(temp, arr)
			res = append(res, arr)
			return
		}
		
		// 尝试第i位填一个数字
		for _, v:= range nums {
			if vis[v] { // 数字已经被选走了忽略
				continue
			}
			
			vis[v]=true  // 标记已经被选走
			dfs(i+1, append(arr, v))
			vis[v]=false // 释放标记，归还到集合中
		}
	}
	
	dfs(0, nil)
	return res
}

练习3 回溯法+剪枝应用组合总和 II

题目链接：力扣

题目大意

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

题目解析

对于一个数字来讲就是选取或者不选取，穷举出所有可能依次判断即可
这里要解决的一个问题是相同的数字有可能被多选，举例[1, 1], 子集中会有2个[1] 这种情况是要去重。
注意剪枝

定义：

定义每一层的状态，当前层待选择的数字是否要选择
定义状态转移操作，待选数字序号加1
定义基础结束条件，所有选择的数字加=target 或所有数字都已经选择完。
剪枝条件：1）所选择数字加和已经大于target, 2) 所选择数字加和加上后面未选择的数字加和小于target

子集去重思路与优化

基本思路
subSet(dep, sum, selected, left) :
	if sum==target: 
		res.push(selected)
		return
	
	if dep >= len(candidates): return // 所有数字选择完
	if sum > target: return // 剪枝条件1
	if sum+left<target: return // 剪枝条件2
	
	// 不选取当前数字
	subSet(dep+1, sum, selected, left-candidates[dep])
	
	// 选取当前数字
	selected.push(candidates[dep])
	subSet(dep+1, sum+candidates[dep], selected, left-candidates[dep])
	selected.pop()
	return 


优化去重逻辑：
假设 [a,b,c] = [1,1,2]
选取过程如下：
[a], [a，b], [a，b，c], [a,c], [b], [b,c](这里已经重复了), [c]
从上面过程中可以看出，选b的时候前面有一个和b相同的元素还没有被选择过说明这个时候还轮不到b来选。

// 优化后 先对candidates排序
subUniqueSet(dep, sum, selected, left) :
	if sum==target: 
		res.push(selected)
		return
	
	if dep >= len(candidates): return // 所有数字选择完
	if sum > target: return // 剪枝条件1
	if sum+left<target: return // 剪枝条件2
	
	
	// 不选取当前数字
	subUniqueSet(dep+1, sum, selected, left-candidates[dep])
	
	// 选取当前数字
	// 判断是否前面有相同数字没有被选择
	if dep>0 && candidates[dep-1]==candidates[dep]: return
	curnum = candidates[dep]
	selected.push(curnum)
	candidates[dep]=-1 //标记被选中了
	subUniqueSet(dep+1, sum+curnum, selected, left-curnum)
	candidates[dep]=curnum //恢复值
	selected.pop()

	return

AC代码

先对candidates排序

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates) // 要先排序。
	res := [][]int{}
	left :=0
	for _, v:= range candidates {
		left += v
	}
	// 优化后 先对candidates排序
	var subUniqueSet func(int, int,  int,[]int)
	subUniqueSet = func(dep, sum, left int, selected []int) {
		if sum==target {
			temp := make([]int , len(selected))
			copy(temp, selected)
			res = append(res, temp)
			return // 后面加正数，肯定要大于target 直接返回
		}

		if dep >= len(candidates){ return} // 所有数字选择完
		if sum > target { return}    // 剪枝条件1
		if sum+left<target{ return }// 剪枝条件2


		// 不选取当前数字
		subUniqueSet(dep+1, sum,left-candidates[dep], selected)

		// 选取当前数字
		// 判断是否前面有相同数字没有被选择
		if dep>0 && candidates[dep-1]==candidates[dep] { return }
		curnum := candidates[dep]
		candidates[dep] = -1 //标记被选中了
		subUniqueSet(dep+1, sum+curnum, left-curnum, append(selected, curnum))
		candidates[dep]= curnum //恢复值
	}
	subUniqueSet(0, 0, left, nil)
	
	return res
}

练习4 记忆化搜索应用矩阵中的最长递增路径

题目链接：力扣

题目大意

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：

输入：matrix = [[1]]
输出：1

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i\][j] <= 2^31 - 1

题目解析

此题类似于最长上升子序列。使用动态规划解决。

定义：

定义状态，dp[i\][j] 表示是以matrix[i\][j] 结尾的最长上升路径的长度。
终止条件：matrix[i\][j] 四周没有比自己小的数字, 或i, j 越界了 (肯定有数字的四周是大于等自己的，所以最终肯定会停止)
转移方程：dp[i\][j] = 1+ max(dp[i-1\][j], dp[i+1\][j], dp[i\][j-1], dp[i\][j+1]) (matrix[i\][j] >matrix[i-1\][j],matrix[i+1\][j], matrix[i\][j-1], matrix[i\][j+1])

AC代码

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var dir = [][]int{
	{0, -1}, {0, 1}, {1, 0}, {-1, 0},
}

func longestIncreasingPath(matrix [][]int) int {
	vis := make(map[int]bool)
	dp := make(map[int]int)
	n, m := len(matrix), len(matrix[0])

	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i < 0 || i >= n || j < 0 || j >= m { // 越界了，默认0
			return 0
		}
		ind := i*1000 + j // 对矩阵一维化编码
		if vis[ind] {
			return dp[ind]
		} // 已经计算过了，直接返回
		vis[ind] = true //标记已经计算
		dp[ind] = 0
		// 检查4个方法取最大值
		//dp[i][j] = 1+ max(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1])
		for _, d := range dir {
			newX, newY := i+d[0], j+d[1]
			if newX < 0 || newX >= n || newY < 0 || newY >= m { // 越界了
				continue
			}
			if matrix[i][j] <= matrix[newX][newY] { // 不能接在自己后面
				continue
			}
			dp[ind] = max(dp[ind], dfs(newX, newY)) //更新最优值
		}

		// 加上自己
		dp[ind] = dp[ind] + 1

		return dp[ind]
	}

	best := 0
	// 检查 每个dp(i,j) 取最大值
	for i, row := range matrix {
		for j := range row {
			//fmt.Printf("%d, ", dfs(i, j))
			best = max(best, dfs(i, j))
		}
		//fmt.Println()
	}

	return best
}

六、总结

主要内容：

深搜算法是一种暴力算法，适用于状态全集规模较小搜索问题。
作用：图应用主要有1）深度优先遍历结点，2）图连通块相关的一些计算，比如判2点是否连通，有几个连通块。

回溯法（剪枝），记忆化搜索也是深搜算法的应用。
解题的基本框架比较固定，关键在于状态的定义，以及状态转移方法的构造。

笔者水平有限，有写得不对或者解释不清楚的地方还望大家指出，我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目（首先AK F.*ing leetcode），给大家准备了一些题目，供大家练习参考。干他F.*ing (Fighting?)。

七、实战训练

代码基础训练题

光说不练假把式，学完了怎么也要实操一下吧，快快动用把刚才那例题A了。

图深度优先遍历应用题目链接力扣
回溯法应用题目链接力扣
回溯法+剪枝应用题目链接力扣
记忆化搜索应用题目链接力扣

AK leetcode

leetcode相关题目都在下面了，拿起武器挨个点名呗。

力扣深度优先遍历

力扣回溯（剪枝）算法

力扣记忆化搜索

以上题目太多，大家适当选择就行，下面还有进阶题目。

大神进阶

hdu

poj

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

在这里插入图片描述

AK F.*ing leetcode 流浪计划之DFS

一、简介

二、作用

三、解题步骤

图遍历应用

回溯法（剪枝）应用

记忆化搜索动态规划应用

四、代码框架

图遍历框架

回溯法（剪枝）框架

记忆化搜索框架

五、牛刀小试

练习1 图深度优先遍历应用 省份数量

题目大意

题目解析

AC代码

练习2 回溯法应用全排列

题目大意

题目解析

AC代码

练习3 回溯法+剪枝应用 组合总和 II

题目大意

题目解析

子集去重思路与优化

AC代码

练习4 记忆化搜索应用 矩阵中的最长递增路径

题目大意

题目解析

AC代码

六、总结

七、实战训练

代码基础训练题

AK leetcode

大神进阶

练习1 图深度优先遍历应用省份数量

练习3 回溯法+剪枝应用组合总和 II

练习4 记忆化搜索应用矩阵中的最长递增路径