【废物研究生零基础刷算法】DFS与递归（一）典型题型

跳台阶

思路：

• 如果 n = 1，只有一种走法（走 1 级）。
• 如果 n = 2，有两种走法（1+1 或 2）。
• 对于 n > 2，到达第 n 级的方法可以分解为：
• 从第 n-1 级走 1 级上来，方案数为 f(n-1)；从第 n-2 级走 2 级上来，方案数为 f(n-2)。
• 因此，总方案数 f(n) = f(n-1) + f(n-2)。

def Fibonacci(x):if x==1: return 1if x==2: return 2return Fibonacci(x-1)+Fibonacci(x-2)n = int(input())
print(Fibonacci(n))

递归实现指数级枚举

思路：

1. 顺序：从1～n依次考虑每个数选/不选，可能的结果是2^n
2. 使用长度为n的数组st来记录每个数是选还是不选：0（不确定选不选）、1（选择）、2（不选择）
3. 传入的参数x代表选择的位置

N = 20  # 数据范围最大 n ≤ 15，定义一个稍大的常量
st = [0] * N  # 初始化 st 数组，长度固定，所有元素为 0
n = int(input())  # 输入 ndef dfs(x):if x > n:  # 当 x 超过 n，说明所有数都考虑完了，输出方案selected = []  # 存储被选择的数字for i in range(1, n + 1):  # 检查 1 到 n 的状态if st[i] == 1:  # 如果选择这个数selected.append(i)if not selected:  # 如果没有选择任何数，输出空行print(" ")else:print(" ".join(map(str, selected)))  # 输出选择的数字，用空格分隔.map(str, selected) 的作用是将 selected 列表中的每个元素（数字）转换为字符串。return# 不选择当前数 xst[x] = 2dfs(x + 1)st[x] = 0  # 回溯，恢复状态为未考虑# 选择当前数 xst[x] = 1dfs(x + 1)st[x] = 0  # 回溯，恢复状态为未考虑dfs(1)  # 从 1 开始

递归实现排列型枚举

思路：

1. 考虑每个位置能存放的数
2. 使用布尔类型的数组st表示当前存放的状态，True表示有该数，False表示没有该数

N = 20  # 常量，稍大于 n 的最大值 15
n = int(input())  # 输入 n
arr = [0] * N  # 存储当前排列的数组
st = [False] * N  # 标记数字是否使用，0 到 n-1 表示数字 1 到 ndef dfs(x):if x > n:  # 当 x 超过 n，说明排列已填满，输出结果result = ""for i in range(1, n + 1):  # 输出 arr[1] 到 arr[n]result += f"{arr[i]:5d}"  # 每个数字占 5 个字符宽度print(result)returnfor i in range(1, n + 1):  # 枚举 1 到 n 的数字if not st[i]:  # 如果数字 i 还未使用st[i] = True  # 标记为已使用arr[x] = i  # 将 i 放入当前位置dfs(x + 1)  # 递归填下一个位置st[i] = False  # 回溯，恢复未使用状态arr[x] = 0  # 回溯，清空当前位置dfs(1)  # 从位置 1 开始填

---

上面两题总结

为什么回溯处理方式不同？

1. 子集问题（指数型枚举）为什么不用for循环？

• 决策方式：对于每个数字 x，只有“选”或“不选”两种固定选择。
• 状态独立：选择 x 不会影响其他数字的可用性，因此不需要遍历所有可能选项，只需直接指定状态（st[x] = 1 或 2）。
• 回溯逻辑：
• • 每次递归只处理一个数字的状态。
• • 直接设置 st[x]，递归后恢复为 0，不需要额外的循环来尝试其他值。
• 本质：这是一个二分支问题（选或不选），每个位置的决策是固定的二选一。

2. 全排列问题为什么用 for 循环？

• 决策方式：对于每个位置 x，需要从剩余未使用的数字中选择一个，而不是简单的二选一。
• 状态依赖：某个数字 i 被选后，后续位置不能再用它，因此需要用 st 检查哪些数字可用。
• 回溯逻辑：
• • 用 for i in range(1, n + 1) 遍历所有数字，检查 st[i] 是否为 False（未使用）。
• • 每次尝试一个可用的 i，标记为已用（st[i] = True），填入 arr[x]，递归后回溯。
• 本质：这是一个多分支问题（从 n 个数字中选一个），每个位置需要动态枚举当前可用的选项。

递归实现组合型枚举

N = 30
n, r = map(int, input().split())  # 一行输入 n 和 r
st = [False] * N  # 标记数字是否使用
arr = [0] * N  # 存储当前组合def dfs(x, start):if x > r:  # 选满 r 个数时输出result = ""for i in range(1, r + 1):  # 输出 arr[1] 到 arr[r]result += f"{arr[i]:3d}"  # 每个数字占 3 个字符宽度print(result)returnfor i in range(start, n + 1):  # 从 start 到 n 枚举if not st[i]:  # 如果 i 未使用st[i] = True  # 标记已使用arr[x] = i  # 放入当前位置dfs(x + 1, i + 1)  # 递归，下一位置从 i+1 开始st[i] = False  # 回溯arr[x] = 0  # 回溯dfs(1, 1)  # 从位置 1 开始，从数字 1 开始选

P1036选数

N = 30
n, k = map(int, input().split())
q = list(map(int, input().split()))  # 输入数组
st = [False] * N  # 标记是否使用
arr = [0] * N  # 存储当前组合
count = 0def is_prime(n):if n < 2:return Falsefor i in range(2, int(n ** 0.5) + 1):if n % i == 0:return Falsereturn Truedef dfs(x, start):global count  # 声明 count 为全局变量if x > k:  # 选满 k 个数sum_val = 0for i in range(1, k + 1):sum_val += arr[i]if is_prime(sum_val):count += 1returnfor i in range(start, n):  # 从 start 到 n-1 枚举数组索引if not st[i]:  # 如果 q[i] 未使用st[i] = Truearr[x] = q[i]  # 存入当前数字dfs(x + 1, i + 1)  # 下一位置，从 i+1 开始st[i] = Falsearr[x] = 0dfs(1, 0)  # 从位置 1 开始，从数组索引 0 开始
print(count)

为什么需要global？

• 函数外定义 ≠ 自动可修改：
• • 在函数外定义 count = 0 只意味着它在全局作用域存在，可以被读取。
• • 但函数内的任何赋值（如 count += 1、count = 5）都会创建一个新的局部变量，除非用 global 声明。
• 保护全局变量：
• • Python 这样设计是为了防止函数意外修改全局状态。如果你想修改，必须明确意图。

如何从索引为1开始存放？

# 读取输入并转换为整数列表
q = list(map(int, input().split()))# 在列表开头插入一个占位元素 0
q.insert(0, 0)# 打印结果
print(q)