算法Python题解——DFS和BFS

目录DFSLEGB原则760数的计算BFSDFS把原问题分解成子问题的结构天然适合用DFS实现DFS的核心特点就是深度优先遍历所有确保遍历每一种方式枚举所有可能的生成路径做DFS需要明确一下几个问题递归出口是深度是作为每一次DFS的节点的变量是LEGB原则要好好学一下LEGB原则Python的变量与作用域等先局部Local→E外部→G全局global→B自带内部对于不可变变量比如普通变量如果赋值/修改操作必须要声明global或nonlocal如果不修改只取值不需要加对于可变变量比如列表字典修改值赋值不需要加global#LEGB原则 #嵌套作用域优先级 a 10 def func1(): a 20 print(a) def func2(): nonlocal a #如果想在嵌套函数内给外层函数的变量赋值需要用nonlocal而非global a 1 print(a)#如果没有上一句nonlocal内层函数无定义直接找外层的a 20 func2() func1() #函数中对于读取和赋值作用域不同读取全局变量√赋值操作默认视为局部变量 ans 0 n 5 visit [] def dfs(): global ans ans1#需要赋值/修改值要加global print(ans) print(n)#仅读取不改动不用global visit.append(1)#列表字典属于可变对象可以随便修改 #visit[n] True #这条会报越界错因为visit是空数组 visit[0] True#不报错 dfs()760数的计算这题按照上面分析的几个问题递归出口是 x 1,x//21 1range(1,1)没有可以添加的数自动终止正好这题不用写if 终止语句 return的模板深度就是初始数n作为每一次DFS的节点的是每次递归的1/2个原数也就是题解中的j当时自己做的时候把ji,n搞混了import os import sys #全局变量 n int(input()) visit [] visit [False] * (n 1)#必须初始化不然越界 ans 0 def dfs(depth,i): global ans#必须得有这句话 ans 1 for j in range(1,i//21):#别忘了·终点都是不包含的 if visit[j] ! True: visit[j] True dfs(depth1,j) visit[j] False dfs(1, n) print(ans)BFS