DFS简介
搜索算法：穷举问题解空间所有情况
深度优先搜索：既暴力枚举，尽可能一条路走到底，走不了再回退
给定一个数字x，将其拆分成3个正整数，后一个要求大于等于前一个，给出方案.
- 就需要实现n重循环
- n重循环=特定的树状结构=DFS搜索
给定一个数字x=6，将其拆分成3个正整数，后一个要求大于等于前一个，给出方案。
DFS模板
def dfs(depth): if depth == n: return
例题：
分糖果
两种糖果分别有9个和16个，要全部分给7个小朋友，每个小朋友得到的糖果总数最少为2个最多为5个，问有多少种不同的分法。糖果必须全部分完。两种糖果分别有9个和16个，要全部分给7个小朋友，每个小朋友得到的糖果总数最少为2个最多为5个，问有多少种不同的分法。糖果必须全部分完。
ans = 0 # 方案数 def dfs(depth, n, m): # 每一层都有枚举 if depth == 7: # 不管还剩多少,dfs都结束了,如果剩余为零则说明ans加一 if n == 0 and m == 0: global ans ans += 1 return for i in range(0, 6): for j in range(0, 6): # i+j是第一个小朋友的全部糖 if 2 <= i + j <= 5 and i <= n and j <= m: dfs(depth + 1, n - i, m - j) dfs(0,9,16) print(ans)
在写dfs函数时，要先写出递归的结束深度，以及在此处的判断，然后写出分糖果的一一枚举情况，最后写出下一层（下一个小朋友）的情况。
买瓜
小蓝正在一个瓜摊上买瓜。瓜摊上共有n个瓜，每个瓜的重量为A;小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。小蓝希望买到的瓜的重量的和恰好为m。请问小蓝至少要劈多少个瓜才能买到重量恰好为m的瓜。如果无论怎样小蓝都无法得到总重恰好为m 的瓜，请输出—1。
输入的第一行包含两个整数n,m，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含n个整数A，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。
def dfs(depth, weight, cnt): # 写之前要明确参数,这是第几个瓜,目前买到的质量是多少,目前劈瓜几次 if weight > m: # 剪枝的出口 return if weight == m: global ans ans = min(ans, cnt) if depth == n: # 正常的出口 return dfs(depth + 1, weight, cnt) dfs(depth + 1, weight + A[depth], cnt) dfs(depth + 1, weight + A[depth] // 2, cnt + 1) n, m = map(int, input().split()) # 买n个瓜,希望买到的总质量为m m *= 2 A = list(map(int, input().split())) A = [x * 2 for x in A] ans = n + 1 # 表示每个挂=瓜都劈一次 dfs(0, 0, 0) if ans == n + 1: ans = -1 print(ans)
- 为了避免除以二造成的精确度缺失，我们对小蓝所期望的总质量m和每个瓜的质量A乘以二，可以默认劈瓜的次数为n+1，如果递归搜索完成还没有得到m，就让ans等于-1。
- 同理depth，weight，cnt分别代表了轮到了第几个瓜，当前搜索到的总质量，劈瓜的次数。
- 我们先写出函数的结束，既depth == n ，然后到了枚举阶段，上个案例是每次分给小朋友的糖果数，这次是根据劈不劈瓜分成三种情况。最后还有剪枝的回退，写入前段部分。
3 10
1 3 13
2
DFS算法及应用（二）+https://developer.aliyun.com/article/1544415?spm=a2c6h.13148508.setting.18.1fa24f0eaie4S4
