017搜索之深度优先DFS——算法备赛

深度优先搜索

如果说广度优先搜索是逐层扩散，那深度优先搜索就是一条道走到黑。
深度优先遍历是用递归实现的，预定一条顺序规则（如上下左右顺序） ，一直往第一个方向搜索直到走到尽头或不满足要求后返回上一个叉路口按第二个方向继续搜索，以此类推，直到所有节点都遍历到。

简单回溯

N皇后

问题描述：

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。

这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

原题链接

思路分析

N皇后问题是dfs的经典问题。

对于每一行，皇后都有N（N列）种放法，对于每一行遍历每一种位置，如果它与前面某一行的皇后处在同一列或同一对角线那就不能摆放在该位置；否则可以摆放在该位置，进行下一行的摆放。

vector<int>x;  //存储第i行皇后所在列
vector<vector<string>>tar;
vector<string>tr;
int sum=0,s;
bool check(int k){for(int i=1;i<k;i++){if(x[k]==x[i]) return false;  //判断该行的皇后是否与前面的皇后在同一列if(abs(x[k]-x[i])==k-i) return false;  //判断该行的皇后是否与前面的皇后在同一对角线}return true;
}
void DFS(int t){if(t>s) {  //当m>s时，该方案满足条件。sum++;  //记录方案数。tar.push_back(tr);}else{for(int i=1;i<=s;i++){x[t]=i;tr[t-1]="";tr[t-1].insert(0,s,'.');tr[t-1][i-1]='Q';  //修改该行状态if(check(t)) DFS(t+1);  //符合条件 开始下一行的摆放。 不合条件则摆在下一列。}}
}
vector<vector<string>> solveNQueens(int n) {s=n;x.resize(n+1);tr.resize(n);DFS(1);  //从第一行开始搜索return tar;
}

路径之迷

蓝桥杯2016年国赛题

描述：

原题链接

代码

#include <bits/stdc++.h>
using namespace std;int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int n;
vector<int>rowCnt, colCnt;
bool allFlat = false;
vector<vector<bool>>vis;
vector<int>tar;bool checkEnd(int row, int col) {if (row != n - 1 || col != n - 1) return false;for (int i = 0; i < n; i++) {if (rowCnt[i]) return false;  //有一个不为0，返回false}for (int i = 0; i < n; i++) {if (colCnt[i]) return false;  //有一个不为0，返回false}allFlat = true;return true;
}bool check(int row, int col) {if (row < 0 || row >= n || col < 0 || col >= n|| vis[row][col]) return false;  //越界或走到已走过的节点if (rowCnt[row] <= 0 || colCnt[col] <= 0) return false;  //箭用完了return true;
}void dfs(int row, int col) {if (checkEnd(row, col) || allFlat) return;  //结束for (int i = 0; i < 4; i++) {int x = row + dx[i];int y = col + dy[i];if (check(x,y)) {vis[x][y] = true;rowCnt[x]--, colCnt[y]--;tar.push_back(x * n + y);  //第x行，第y列的节点编号为 x * n + ydfs(x, y);if (allFlat) return;  //allFlat为true，不用继续执行了vis[x][y] = false;  //回溯，还原现场rowCnt[x]++, colCnt[y]++;tar.pop_back();}}
}
int main()
{cin >> n;rowCnt = vector<int>(n);colCnt = vector<int>(n);vis = vector<vector<bool>>(n, vector<bool>(n));for (int i = 0; i < n; i++)cin >> colCnt[i];for (int i = 0; i < n; i++)cin >> rowCnt[i];vis[0][0] = 1;colCnt[0]--;rowCnt[0]--;tar.push_back(0);dfs(0, 0);for (auto i : tar) {cout << i << " ";}return 0;
}

简单正则问题

蓝桥杯2017年省赛题

问题描述

考虑一种简单的正则表达式：只由 x,(,),| 组成的正则表达式。求这个正则表达式能接受的最长字符串的长度？

例((xx|xxx)x|(x|xx))xx 能接受的最长字符串是xxxxxx，长度是6.

原题链接

思路分析

1. ()规定了运算的优先级最高，|代表长度取max，x代表一个字符
2. 根据嵌套规则，设计dfs
3. 自底向上画出问题的二叉树，以((xx|xxx)x|(x|xx))xx 为例

代码

#include<bits/stdc++.h>using namespace std;string s; 
int k = 0;int dfs()
{int res = 0; //统计当前层可以容纳多少xwhile(k < s.size()){if(s[k] == '('){k++;  //跳过左括号res += dfs();  //遇到括号，把括号中的值求出，再与res做+运算 k++; //跳过右括号}else if(s[k] == '|'){k++; //跳过 或 运算res = max(res, dfs()); //遇到或运算，把|右边的求出，再与res做max运算}else if(s[k] == ')') break; else{k++; res++;  //遇到单个x，res直接加1}}return res;
}int main()
{cin >> s;cout << dfs() << endl;return 0;
}

记忆化搜索

掷骰子等于目标数的方法数

问题描述

这里有 n 个一样的骰子，每个骰子都不一样，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果中（总共有 k^n 种方式），使得骰子面朝上的数字总和等于 target的结果数。

由于答案可能很大，你需要对 109 + 7 取模。

原题链接

思路分析

枚举第n个筛子的点数为x，那么这种情况的结果数就是前 n-1个筛子点数和为target-x的结果数。

那可以很自然地想到定义dp[i][j]表示前i个筛子点数和为j的结果数，dp[i][j]=sum(dp[i-1][j-x]) , x为枚举的第i个筛子的点数。

动态规划的过程可以使用直观一点的记忆化搜索。

代码

int numRollsToTarget(int n, int k, int target) {int mod=1e9+7;vector<vector<int>>dp(n+1,vector<int>(target+1));auto dfs=[&](auto dfs,int st,int sum)->int{if(dp[st][sum]) return dp[st][sum];if(st==n){if(sum<=k){dp[n][sum]=1;return 1;}}int l=max(1,sum-(n-st)*k);int r=min(k,sum-(n-st));for(int i=l;i<=r;i++){dp[st][sum]=(dp[st][sum]+dfs(dfs,st+1,sum-i))%mod;}return dp[st][sum];};return dfs(dfs,1,target);
}

统计满足逆序对数量条件的排列数量

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。

整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ：

• i < j 且 nums[i] > nums[j]

请你返回 [0, 1, 2, ..., n - 1] 的 排列 perm 的数目，满足对 所有 的 requirements[i] 都满足 perm[0..endi] 中恰好有 cnti 个逆序对。

由于答案可能会很大，将它对 109 + 7 取余 后返回。

思路分析

首先将问题分解为子问题。考虑示例{n = 3, requirements = [[2,2],[0,0]] }，整个排列 [0,2] 恰好要有 2 个逆序对。分情况进行讨论：

• 末尾元素为 0。由于 0 是最小元素，前面的两个元素，每个元素都会与 0 构成一对逆序对。此时，[0,1] 还需要贡献 0 对逆序对。
• 末尾元素为 1。前面的两个元素中，2 会与 1 构成一对逆序对。此时，[0,1] 还需要贡献 1 对逆序对。
• 末尾元素为 2。前面的两个元素中，任何元素都不能和 2 构成逆序对。此时，[0,1] 还需要贡献 2 对逆序对。

定义函数 dfs(end,cnt)，用来计算排列逆序对为 cnt 且满足 requirements 的排列 perm[0…end] 的个数。代入示例 ，我们可以得到 dfs(2,2)=dfs(1,0)+dfs(1,1)+dfs(1,2) 的递推公式。

更一般地，计算dfs(end,cnt)，我们可以得到以下递推公式：

• 如果 [0,end−1] 在 requirements 有要求逆序对数量，且对应的逆序对要求数量为 r，那么我们在计算 dfs(end,cnt)时，因为[0,end-1]的逆序对个数为r，前面的元素需要与最后一个元素贡献 cnt−r 个逆序对，因为排列的每个元素都不一样，最后一个元素的取值要么不存在，要么唯一确定。这个逆序对的个数满足 0≤cnt−r≤end。因此，当满足 r≤cnt≤end+r 时，dfs(end,cnt)=dfs(end−1,r)；否则，dfs(end,cnt)=0。
• 如果 end−1 不在 requirements 有要求。那么我们遍历末尾元素所有的可能性。遍历的范围为 0∼min(end,cnt)，得到递推公式 dfs(end,cnt)=∑ i=0，min(end,cnt) dfs(end−1,cnt−i)。

注意需要对 dfs 应用记忆化搜索,定义数组memo，meno[i][j]存储dfs(i,j)的计算结果，这样每个状态最多被计算一次，降低时间复杂度。

最后返回 dfs(n−1,reqMap[n−1])即可，其中 reqMap 是将 requirements 转化成的键值对，键为 endi，值为 cnti。

代码

int numberOfPermutations(int n, vector<vector<int>>& requirements) {const int MOD = 1e9+7;vector<int> req(n, -1);req[0] = 0;for (auto& p : requirements) {req[p[0]] = p[1];}if (req[0]) {return 0;}int m = ranges::max(req);vector<vector<int>> memo(n, vector<int>(m + 1, -1)); // -1 表示没有计算过auto dfs = [&](auto&& dfs, int i, int j) -> int {if (i == 0) {return 1;  //i为0，直接返回1}int& res = memo[i][j]; // 注意这里是引用if (res != -1) { // 之前计算过return res;}res = 0;if (int r = req[i - 1]; r >= 0) {  //r大于0，说明在req中有逆序对数量要求if (j >= r && j <= r + i) {  //对于满足要求的j，res值唯一确定，继承前者dfs(i-1,r)。res = dfs(dfs, i - 1, r);}} else {for (int k = 0; k <= min(i, j); k++) {  //前面元素和当前最后一位组成k对逆序对，最多不会超过i。res = (res + dfs(dfs, i - 1, j - k)) % MOD;  //对于每个枚举的k，前面元素需组成j - k对逆序对}}return res;};return dfs(dfs, n - 1, req[n - 1]);}

剪枝技巧

组合总数

问题描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

原题链接

代码

vector<vector<int>>tar;vector<int>tr;int s;void dfs(vector<int>& c,int begin,int t){if(t==0) {tar.push_back(tr);return;}/*在搜索中去重，每一次搜索的时候设置 下一轮搜索的起点 begin从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。*/for(int i=begin;i<s&&t-c[i]>=0;i++){  //t-c[i]>=0,减枝tr.push_back(c[i]);dfs(c,i,t-c[i]);  tr.pop_back();  //回朔}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {s=candidates.size();if(s==0) return tar;sort(candidates.begin(),candidates.end());  //排序是剪枝的前提dfs(candidates,0,target);return tar;}

买瓜

蓝桥杯2023年省赛题

问题描述

小蓝在瓜摊上买瓜。瓜摊上共有n个瓜，每个瓜的重量为Ai，小蓝可以把任何瓜劈成完全等重的两份，不过每个瓜最多劈一刀。小蓝希望买的瓜的重量之和为m。输出小蓝至少要劈多少个瓜才能买到总重量恰好为m的瓜，如果无论如何都无法得到总重量恰好为m的瓜，则输出-1。

原题链接

思路分析

每个西瓜可以有1.选整个，2.不选，3.选一半 三种选择，枚举所有总重量等于m的组合方案，选出劈瓜数最少得那个。如果纯暴力的话，总复杂度将达到O(3^n).

可通过剪枝来优化一下时间复杂度：

1. 选取的瓜的总重量已经大于等于m，可以不用继续【递】下去，直接【归】。
2. 维护一个最小劈瓜数ans，当前劈瓜数已经大于等于ans时不用再【递】下去，直接【归】。
3. 定义一个后缀数组sum，记录sum[i]记录[i,n-1]区间内所有西瓜的总重量，当前面选取西瓜重量+后面所有西瓜总重量都不足以等于m时不用再【递】下去，直接【归】。

代码

#include <bits/stdc++.h>
using namespace std;int ans=50;//ans维护最小劈瓜数  先设为一个大值int a[50];//存瓜 原数组int sum[50];//表示的是从第 i 个瓜到第 n 个瓜的总质量int n,m;void dfs(int S,int i,int cnt)//总和，下标，劈瓜计数器
{if(cnt>=ans)return;//剪枝if(S==m) ans=min(ans,cnt);//如果相等，说明劈瓜劈够了，返回已经劈了几次瓜if(i>=n||S>=m||S+sum[i]<m) return ;//递归结束条件dfs(S+a[i],i+1,cnt);//买一个瓜dfs(S+a[i]/2,i+1,cnt+1);//买半个瓜，计数器+1dfs(S,i+1,cnt);//不买当前瓜，跳到下一个瓜
}
int main()
{ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m;m<<=1;//总质量也要*2才能保证结果不受影响for(int i=0;i<n;i++) cin>>a[i],a[i]<<=1;//为了防止劈瓜出现小数，将其左移一位*2倍//遍历所有的瓜for(int i=n-1;i>=0;i--){sum[i]=sum[i+1]+a[i];//记录后缀数组}dfs(0,0,0);if(ans==50)cout<<-1;  //最终 ans 仍然为初始值 50，则表示无法通过劈瓜的方式满足要求else cout<<ans;return 0;
}