笔记：蓝桥杯python搜索（3-2）——DFS剪支和记忆化搜索

目录

 一、DFS剪支

二、例题

P2942 数字王国之军训军队

 P3075 特殊的多边形

三、记忆化搜索

四、例题

例题 P3820 混境之地

P216 地宫取宝

---

 一、DFS剪支

• 在搜索过程中，如果需要完全遍历所有情况可能需要很多时间
• 在搜索到某种状态时，根据当前状态判断出后续无解，则该状态无需继续深入搜索
• 例如：给定N个正整数，求出有多少个子集之和小于等于K。在搜索过程中当前选择的数字和已经超过K则不需要继续搜索。
• 可行性剪枝：当前状态和题意不符，并且往后的所有情况和题意都不符，那么就可以进行剪枝。
• 最优性剪枝：在搜索过程中，当前状态已经不如已经找到的最优解，也可以剪枝，不需要继续搜索。

二、例题

P2942 数字王国之军训军队

数字王国开学了，它们也和我们人类一样有开学前的军训，现在一共有 n 名学生，每个学生有自己的一个名字 ai​（数字王国里的名字就是一个正整数，注意学生们可能出现重名的情况），此时叛逆教官来看了之后感觉十分别扭，决定将学生重新分队。

排队规则为：将学生分成若干队，每队里面至少一个学生，且每队里面学生的名字不能出现倍数关系（注意名字相同也算是倍数关系）。

现在请你帮忙算算最少可以分成几队？

例：有 4 名学生 (2,3,4,4)，最少可以分成 (2,3)、(4)、(4) 共 3 队。

输入格式

第一行包含一个正整数 n，表示学生数量。

第二行包含 n 个由空格隔开的整数，第 i 个整数表示第 i 个学生的名字 ai​。

输出格式

输出共 1 行，包含一个整数，表示最少可以分成几队。

DFS 搜索，枚举每个学生分到每个组内

可行性剪枝：要满足题目条件

最优性剪枝：判断当前状态是否比 ans 更劣

---

def check(x,group):for y in group:if x%y ==0 or y%x==0:return Falsereturn Truedef dfs(depth):if depth==n:global answeranswer=min(answer,len(Groups))returnfor every_group in Groups:if check(a[depth],every_group):every_group.append(a[depth])dfs(depth+1)every_group.pop()Groups.append([a[depth]])dfs(depth+1)Groups.pop()n=int(input())
a=list(map(int,input().split()))
Groups=[]
answer=n
dfs(0)
print(answer)

# 判断x能否加入group组   
def check(x, group):# 要保证不能存在倍数关系for y in group:if x % y == 0 or y % x == 0:return Falsereturn True# depth表示当前为第depth个学生   
def dfs(depth):global ans# 最优性剪枝：当前已经比ans大，说明该策略不可行if len(Groups) > ans:returnif depth == n:ans = min(len(Groups), ans)returnfor each_group in Groups:# 枚举第depth个学生能否加入当前组each_group# 剪枝：必须满足题意if check(a[depth], each_group):each_group.append(a[depth])dfs(depth + 1)each_group.pop()# 单独作为一组，将 ​a[depth]​ 作为一个新的分组添加，即 ​Groups.append([a[depth]])​Groups.append([a[depth]])dfs(depth + 1)Groups.pop()n = int(input())   
a = list(map(int, input().split()))   
# ans表示最少能分多少队   
ans = n# Groups表示分组情况   
Groups = []   
dfs(0)   
print(ans)

 P3075 特殊的多边形

假设一个 n 边形 n 条边为 a1,a2,a3,⋯,an​，定义该 n 边形的值 v=a1×a2×a3×⋯×an。

定义两个 n 边形不同是指至少有一条边的长度在一个 n 边形中有使用而另一个 n 边形没有用到，如 n 边形 (3,4,5,6)和 (3,5,4,6) 是两个相同的 n 边形，(3,4,5,6)和 (4,5,6,7) 是两个不相同的 n 边形。

现在有 t 和 n，表示 t 个询问并且询问的是 n 边形，每个询问给定一个区间 [l,r]，问有多少个 n 边形（要求该 n 边形自己的 n 条边的长度互不相同）的值在该区间范围内。

输入格式

第一行包含两个正整数 t、n，表示有 t 个询问，询问的是 n 边形。

接下来 t 行，每行有两个空格隔开的正整数 l、r，表示询问区间 [l,r]。

输出格式

输出共 t 行，第 i行对应第 i 个查询的 n 边形个数。

• 先考虑简单版：乘积为 v 有多少种 n 边形

• DFS 处理出所有乘积对应的所有可能

  • 维护一个递增的边长序列（唯一性）

  • 枚举第 i 边的长度，最小最大范围（剪枝）

  • 最终 check 是否满足 N 边形：

    • 最小的 N - 1 条边之和大于第 N 边

• 预处理+前缀和 O(1)查询答案

---

import os
import sys# 请在此输入您的代码
def dfs(depth, last_val, tot, mul):""":param depth:    第depth条边长:param last_val: 上一边长长度:param tot:      累计和:param mul:      累计乘积"""if depth == n:# 前n-1条边之和大于第n条边if tot - path[-1] > path[-1]:ans[mul] += 1returnfor i in range(last_val + 1, 100001):# 最优性剪枝, 后续还有n-depth个数字, 每个数字都要>=i# 累计乘积要不超过100000: mul * (i ** (n - depth))if mul * (i ** (n - depth)) > 100000:breakpath.append(i)dfs(depth + 1, i, tot + i, mul * i)path.pop()t, n = map(int, input().split())
ans = [0] * 100001
path = []
dfs(0, 0, 0, 1)for i in range(1, 100001):ans[i] += ans[i - 1]
for _ in range(t):l, r = map(int, input().split())print(ans[r] - ans[l - 1])

三、记忆化搜索

• 记忆化：通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。
• 记忆化=dfs+额外字典
  • 如果先前已经搜索过：直接查字典，返回字典中结果
  • 如果先前没有搜索过：继续搜索，最终将该状态结果记录到字典中

• 斐波那契数列：设F[0] = 1, F[1] = 1, F[n] = F[n - 1] + F[n - 2]，求F[n]，结果对1e9 + 7取模。 0 <= n <= 10000
• 样例输入： 5000
• 样例输出： 976496506

def f(n):if n==0 or n==1:return 1return (f(n-1)+f(n-2))%(1e9+7)
n=int(input())
print(f(n))
# 直接递归存在大量重复计算

计算 F(5) 时，要先算 F(4) 和 F(3)；算 F(4) 又需算 F(3) 和 F(2)，这里 F(3) 就被重复计算了。随着 n 增大，像 F(2)、F(3) 这类中间结果会被反复多次计算，导致时间复杂度呈指数级增长，效率极低。

• 每次搜索时将当前状态答案记录到字典中
• 后续搜索直接返回结果

import sys
sys.setrecursionlimit(100000)# 记忆化1
dic={0:1,1:1}
def f(n):if n in dic.keys():return dic[n]dic[n]=(f(n-1)+f(n-2))%1000000007return dic[n]
n=int(input())
print(f(n))

 

from functools import lru_cache#记忆化搜索2
@lru_cache(maxsize=None)

from functools import lru_cache# 记忆化2
@lru_cache(maxsize=None)
def f(n):if n==0 or n==1:return 1return f(n-1)+f(n-2)
n=int(input())
print(f(n))

四、例题

例题 P3820 混境之地

小蓝有一天误入了一个混境之地。

好消息是：他误打误撞拿到了一张地图，并从中获取到以下信息：

1. 混境之地是一个 n⋅m 大小的矩阵，其中第 i 行第 j 列的的点 hij​ 表示第 i 行第 j 列的高度。

2. 他现在所在位置的坐标为 (A,B) ，而这个混境之地出口的坐标为 (C,D) ，当站在出口时即表示可以逃离混境之地。

3. 小蓝有一个喷气背包，使用时，可以原地升高 k 个单位高度。

坏消息是：

1. 由于小蓝的体力透支，所以只可以往低于当前高度的方向走。

2. 喷漆背包燃料不足，只可以最后使用一次。

小蓝可以往上下左右四个方向行走，不消耗能量。

小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，输入 Yes ，反之输出 No 。

---

输入格式

第 1 行输入三个正整数 n,m 和 k ， n,m 表示混境之地的大小， k 表示使用一次喷气背包可以升高的高度。

第 2 行输入四个正整数 A,B,C,D ，表示小蓝当前所在位置的坐标，以及混境之地出口的坐标。

第 3 行至第 n+2 行，每行 m 个整数，表示混境之地不同位置的高度。

输出格式

输出数据共一行一个字符串：

• 若小蓝可以逃离混境之地，则输出 Yes 。

• 若小蓝无法逃离混境之地，则输出 No 。

走到(x,y)，z表示是否使用喷气背包

当x,y,z固定时，具有唯一解，因此可以使用记忆化搜索

时间复杂度<x,y,z>三元组数量：1000*1000*2

from functools import lru_cache#记忆化搜索2
@lru_cache(maxsize=None)
def dfs(x, y, z):# print(x, y, z)# 当前处于(x,y), z表示是否使用喷气背包# 如果能逃离, 返回True, 否则返回Falseif x == C - 1 and y == D - 1:return True#没走到终点，四个方向判断for i in range(4):xx, yy = x + dir[i][0], y + dir[i][1]#不能越界if xx < 0 or xx >= n or yy < 0 or yy >= m:continue#新坐标比旧坐标低，走到新坐标（xx,yy)if Map[xx][yy] < Map[x][y]:if dfs(xx, yy, z):return True#在（x,y)处使用喷气背包elif Map[xx][yy] < Map[x][y] + k and z == False:if dfs(xx, yy, True):return Truereturn False# 四个方向
dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
n, m, k = map(int, input().split())
A, B, C, D = map(int, input().split())
Map = []
for i in range(n):Map.append(list(map(int, input().split())))
if dfs(A - 1, B - 1, False):print("Yes")
else:print("No")

P216 地宫取宝

X 国王有一个地宫宝库。是 n×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。

---

输入描述

输入一行 3 个整数，用空格分开：n,m,k (1≤n,m≤50,1≤k≤12)。

接下来有 n 行数据，每行有m 个整数 Ci (0≤Ci≤12) 代表这个格子上的宝物的价值。

输出描述

要求输出一个整数，表示正好取 k 个宝贝的行动方案数。该数字可能很大，输出它对 10^9+7 取模的结果。

从(x,y)出发，先前已经有宝物z件，已有的最大宝物价值为w的方案数记为dfs(x,y,z,w)

只要确定四元组，就确定当前的方案数

答案=dfs(1,1,0,-1)

最终点=dfs(n,m,z,?) or dfs(n,m,z - 1,?)

(x,y)处可选，可不选，然后可以往右走或者往下走

from functools import lru_cache@lru_cache(maxsize=None)   
def dfs(x, y, z, w):#从(x,y)出发，先前已有z件宝物，已有宝物最大价值为w#走到终点if x == n and y == m:#当前不需要选择if z == k:return 1#当前需要选择if z == k - 1:if w < a[x][y]:return 1#其他情况，均为0return 0ans = 0#遍历两个方向for delta_x, delta_y in [(1, 0), (0, 1)]:xx, yy = x + delta_x, y + delta_yif xx <= n and yy <= m:# 当前不选择ans += dfs(xx, yy, z, w)# 当前选择if w < a[x][y]:ans += dfs(xx, yy, z + 1, a[x][y])return ans % 1000000007n, m, k = map(int, input().split())   
a = [[0]*(m+1)]   
for i in range(n):a.append([0] + list(map(int, input().split())))   
print(dfs(1, 1, 0, -1))