目录
1 DFS简介
1.1 DFS与n重循环
DFS 就是枚举 和n重循环
1.2 代码实现
#dfs和n重循环
x = int(input())
n = int(input())
path = [0]*n
#depth从0开始哦！！！
def dfs(depth):
#depth表示当前的深度！
#采用递归的思想
#写递归出口
if depth == n:
for i in range(1,n):
if path[i] >= path[i-1]:
continue
else:
return
if sum(path) != x:
return
print(path)
return
else:
for i in range(1,x+1):
path[depth] = i
dfs(depth+1)
dfs(0)
1.3 例题
1.3.1 分糖果
#糖果总数
#一共有7个小朋友，9个第一种糖果，16个第二种糖果
ans = 0
def dfs(depth,n,m):
#depth当前是第几个小朋友
#n表示剩余几个第一种
#m表示剩余几个第二种
if depth == 7:
if n==0 and m==0:
global ans
ans +=1
# print(ans)
return
else:
for i in range(0,6):
for j in range(0,6):
if 2<=i+j<=5 and i <=n and j<=m:
dfs(depth+1,n-i,m-j)
dfs(0,9,16)
print(ans)
1.3.2 买瓜
#买瓜
def dfs(depth,weight,cnt):
#depth表示第depth个瓜
#weight表示当前的重量
#cnt表示砍了几刀
if weight > m:
return
if weight == m:
global ans
ans = min(ans,cnt)
if depth == n:
return
else:
#买全部
dfs(depth+1,weight+a[depth],cnt)
#卖一半
dfs(depth+1,weight+a[depth]//2,cnt+1)
#没买
dfs(depth+1,weight,cnt)
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
weight = 0
cnt = 0
m*=2
a = [i*2 for i in a]
ans = n+1
dfs(0,0,0)
if ans == n+1:
ans = -1
print(ans)2 回溯
2.1 定义
2.2 代码实例
2.1.1 排列数
回溯：判断是否能选、打标记、记录路径、下一层、回到上一层？？（是怎么回去的啊老铁）清楚标记、清楚路径储存
回到上一层：通过debug我得出：回到上一层其实是递归自己过程中的实现
递归会造成多个函数的运行，只有运行完才会结束！语言描述能力有限，具体可以自己debug一下感受
n = int(input())
vis = [False]*(n+1)
path = []
def dfs(depth):
if depth == n:
print(path)
return
else:
for i in range(1,n+1):
if vis[i]: #如果已经被标记过就不选这个数直接跳出循环！
continue
vis[i] = True
path.append(i)
dfs(depth+1)
vis[i] = False
path.pop(-1)
dfs(0)2.1.2 找子集
和买瓜一样，瓜是这个瓜买不买，
子集是，这个数选不选 一模一样！！！哦哦哦
找到人任意集合的所有子集
#求子集
#和卖瓜的一样
n = int(input())
a = list(map(int,input().split()))
path = []
def dfs(depth):
if depth ==n:
print(path)
return
else:
#选的话
path.append(a[depth])
# print(path)
dfs(depth+1)
path.pop(-1)
#不选的话
dfs(depth+1)
dfs(0)
2.3 例题
2.3.1 N皇后
不能在同一行同一列和对角线上
# N皇后
#主要是对角线的处理，如果在主对角线上 横纵坐标的值相加为0，在副对角线上横纵坐标相减为0
n = int(input()) #表示有几个皇后
ans = 0
vis1 = [False]*(n+1)
vis2 = [False]*2*(n+1)
vis3 = [False]*2*(n+1)
def dfs(x): #x表示第几行
if x==n:
global ans
ans +=1
return
else:
for y in range(0,n):
#判断是否能放
if vis1[y] is False and vis2[x+y] is False and vis3[x-y+n] is False:
vis1[y] = vis2[x+y] = vis3[x-y+n] = True
dfs(x+1)
vis1[y] = vis2[x + y] = vis3[x - y+n] = False
else:
continue
dfs(0)
print(ans)2.3.2 小朋友崇拜圈
就是要围成一个圈！图论的知识相关
从1出发 开始找环，length用于记录步长--走到之后判断是否可以走，如果不可以走说明到了原来走过的点了
#小朋友崇拜环
import sys
sys.setrecursionlimit(10000000) #例如这里设置为十万
def dfs(x,length):
#从x出发找环
#length走了多少步
vis[x] = length #这个点走了一步现在
#接下来走下面的点了
if vis[a[x]] != 0:
#说明在a[x]这一点形成环了，那么这个点出的length值应该是第一步！
global ans
ans = max(ans,length - vis[a[x]] +1)
return
#说明下一个点已经走过了
#这时就要输出环长了
else:
#说明可以走
dfs(a[x], length+1) #步长加1
n = int(input())
a = [0] + list(map(int,input().split()))
vis = [0]*(n+1) #标记该点是否走过
ans = 0
an = []
for i in range(1,n+1):
dfs(i,1)
print(ans)
2.3.3 全球变暖
高地：上下左右都是#
对于每一个#都看看是不是高地
思路：
1、从左到右 从上到下，对于未标记的陆地“#”做一遍dfs
2、dfs目的：拓展可以到达的所有点，并打上标记
3、可以统计出有多少个岛屿、有多少个高地（上下左右都是#）
#全球变暖
import sys
sys.setrecursionlimit(10000000) #例如这里设置为十万
def dfs(x,y):
#表示现在搜索的点的坐标
#标记该点
vis[x][y]=1
#判断是不是高低
if a[x-1][y] == "#" and a[x+1][y] == "#" and a[x][y-1] == "#" and a[x][y+1] == "#" :#说明上下左右都是高低不会被淹没
global flag
flag = True
#把四周的未遍历的土地继续遍历!!!!!!!
#所有连在一起的就是一座岛屿
#这个坐标周围如果还有陆地说明他们是一个岛屿 没有结束，接着运行！！！！！！！！！！！！
for i in range(4):
xx,yy = x+dir[i][0],y+dir[i][1]
if 0<=xx <=n-1 and 0<= yy<=n-1:
if a[xx][yy] == "#" and vis[xx][yy] == 0:
dfs(xx,yy)
else:
continue
#先写输入
dir = [(1,0),(0,1),(-1,0),(0,-1)]
n = int(input())
a = []
vis = [] #表示标记
flag = False#表示是否是高地！
for i in range(n):
a.append(list(input()))
vis.append([0]*n)
ans = 0
for i in range(n):
for j in range(n):
if a[i][j] == "#" and vis[i][j] == 0:
flag = False
dfs(i,j)
if flag is False:
ans += 1
print(ans)3 剪枝
3.1 定义
当前状态无解就不要向下搜索了
3.2 分类
3.3 例子
3.3.1 数字王国之军训练队
把学生分组：
则dfs的参数就是学生
#数字王国之军训练队
#学生分成多少组？--学生————所以depth是学生
n = int(input())
a = list(map(int,input().split()))
group = []
def check(x,group):
for y in group:
if x%y==0 or y%x== 0 or x==y:
return False
return True
def dfs(depth):
if depth == n:
global ans
ans = min(ans,len(group))
# print(group)
return ans
#放入已有的组中
for ever_group in group:
if check(a[depth],ever_group):
ever_group.append(a[depth])
dfs(depth+1)
ever_group.pop(-1)
#自己变成一个组
group.append([a[depth]])
dfs(depth+1)
group.pop(-1)
#最后要输出一个最小组数
ans = n
dfs(0)
print(ans)
3.3.2 特殊的多边形
#剪枝-特殊的多边形
import sys
sys.setrecursionlimit(100000) #例如这里设置为十万
t,n = list(map(int,input().split()))
a = []
for i in range(t):
a.append(list(map(int,input().split())))
# print(a)
def dfs(depth,last_i,tot,mul,list):
if depth == n:
if tot > 2*path[-1] and list[0] <= mul <= list[1]:
global ans
ans += 1
# print(path)
return
else:
for i in range(last_i+1,100001):
if mul*(i**(n-depth)) <= list[1]:
path.append(i)
dfs(depth+1,i,tot+i,mul*i,list)
path.pop(-1)
else:
break
for list in a:
path = []
ans = 0
dfs(0,1,0,1,list)
print(ans)4 记忆化搜索
4.1 定义
4.2 例子
4.2.1 斐波那契数列
考虑使用递归写法，直接递归的时间是指数级别增加的
重复计算的地方发在字典里！
#斐波那契数列
#没有存储的写法
def f(n):
if n==0:
return 1
if n==1:
return 1
else:
return f(n-1)+f(n-2)
n = int(input())
print(f(n))
#存储的写法
dict={0:1,1:1}
def f(n):
if n in dict.keys():
return dict[n]
else:
dict[n] = f(n-1)+f(n-2)
return dict[n]
print(f(40))但是有一个更牛*的
记忆化搜索的第二种方法
#实现把普通的递归变成记忆化的递归
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
if n==0:
return 1
if n==1:
return 1
else:
return f(n-1)+f(n-2)
n = int(input())
print(f(n))4.2.2 混沌之地
dfs的参数确定 ：坐标
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x,y,z):
#x,y 表示当前的坐标
#z表示喷气背包有没有用
if x == c and y==d:
return True
else:
for detle_x,detle_y in [(0,1),(1,0),(-1,0),(0,-1)]:
xx = x+detle_x
yy = y+detle_y
if 0<=xx<=n-1 and 0<=yy<=m-1:
if A[xx][yy] <A[x][y]:
dfs(xx,yy,z)
if A[xx][yy] <A[x][y]+k and z==False:
dfs(xx,yy,True)
return False
#输入
n,m,k = list(map(int,input().split()))
a,b,c,d = list(map(int,input().split()))
a -=1
b -=1
c -=1
d -=1
A = []
for i in range(n):
A.append(list(map(int,input().split())))
#输出
out = dfs(a,b,False)
if out == True:
print("Yes")
else:
print("No")
'''
5 5 30
1 1 5 5
3 20 13 12 11
19 17 33 72 10
12 23 12 23 9
21 43 23 12 2
21 34 23 12 1
'''
4.2.3 地宫取宝
####当没有不使用记忆搜素，并且加入的是当前位置的val值时
def dfs(x,y,tot,w) : #在（x,y)的数量tot,最大价值为w
if x==n and y==m :
global ans
if tot==k:
ans +=1
return
return
for delta_x,delta_y in [(0,1),(1,0)]:
xx,yy=x+delta_x,y+delta_y
if 0<=xx<=n and 0<=yy<=m:
if w < val[xx][yy]: #把上一个位置的value加进去了
dfs(xx,yy,tot+1,val[xx][yy])
dfs(xx, yy, tot, w) # 不选择
else:
continue
return
n,m,k=map(int,input().split())
val=[[0]*(m+1)]
for i in range(n):
val.append([0]+list(map(int,input().split())))
print(val)
ans = 0
dfs(1,1,1,1)
dfs(1,1,0,-1)
print(ans)###当不使用记忆力搜索，加入的是上一个位置的val值
def dfs(x,y,tot,w) : #在（x,y)的数量tot,最大价值为w
if x==n and y==m :
global ans
if tot==k:
ans +=1
return
elif tot==k-1 and w<val[n][m]:
ans+=1
return
return
for delta_x,delta_y in [(0,1),(1,0)]:
xx,yy=x+delta_x,y+delta_y
if 0<=xx<=n and 0<=yy<=m:
if w < val[x][y]: #把上一个位置的value加进去了
dfs(xx,yy,tot+1,val[x][y])
dfs(xx, yy, tot, w) # 不选择
else:
continue
return
n,m,k=map(int,input().split())
val=[[0]*(m+1)]
for i in range(n):
val.append([0]+list(map(int,input().split())))
print(val)
ans = 0
dfs(1,1,0,-1)
print(ans)###当使用记忆力搜索时！！！！【和之前所有的不同的就是return一定要有返回值！！！不能是空了，要不然记忆什么 我请问呢小姐姐】
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x,y,tot,w) : #在（x,y)的数量tot,最大价值为w
if x==n and y==m :
if tot==k:
return 1
elif tot==k-1 and w<val[n][m]:
return 1
return 0
ans =0
for delta_x,delta_y in [(0,1),(1,0)]:
xx,yy=x+delta_x,y+delta_y
if 0<=xx<=n and 0<=yy<=m:
if w < val[x][y]: #把上一个位置的value加进去了
ans +=dfs(xx,yy,tot+1,val[x][y])
ans +=dfs(xx, yy, tot, w) # 不选择
else:
continue
return ans
n,m,k=map(int,input().split())
val=[[0]*(m+1)]
for i in range(n):
val.append([0]+list(map(int,input().split())))
print(dfs(1,1,0,-1))
本文含有隐藏内容，请 开通VIP 后查看