目录
DFS
LEGB原则
760数的计算
BFS
DFS
把原问题分解成子问题的结构，天然适合用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 ans+=1#需要赋值/修改值，要加global print(ans) print(n)#仅读取不改动，不用global visit.append(1)#列表，字典属于可变对象，可以随便修改 #visit[n] = True #这条会报越界错，因为visit是空数组 visit[0] = True#不报错 dfs()760数的计算
这题按照上面分析的几个问题
- 递归出口是 x = 1,x//2+1 =1，range(1,1)，没有可以添加的数，自动终止（正好这题不用写if 终止语句 return的模板）
- 深度就是初始数n
- 作为每一次DFS的节点的是每次递归的1/2个原数，也就是题解中的j（当时自己做的时候把j，i,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//2+1):#别忘了·终点都是不包含的 if visit[j] != True: visit[j] = True dfs(depth+1,j) visit[j] = False dfs(1, n) print(ans)
