Solves

Appearance

深度优先搜索(Depth First Search) ​

DFS 是图遍历算法的一种。用一句话概括就是：“一直往下走，走不通回头，换条路再走，直到无路可走”。递归算法是深搜算法的实现前提。因此，大家在学习深搜时应具备递归的相应知识。不过，深搜是有一定的搜索框架和程式的，在学习上希望大家能够仔细研究例题，总结规律，多加练习。

  • DFS 搜索的关键：搜索的顺序

问题 1：体积

给出 n 件物品，每件物品有一个体积 vi，求从中取若干件物品能够组成的不同的体积之和有多少种可能？例如 n=3，vi={1,3,4}，那么结果为 6。n≤20,1≤vi≤50

分析：对于每一个物体而言，都有两种情况：选或不选。这样来说我们使用基本的组合数学的知识就可以简单的计算出方案数为 2n，需要注意的是我们不能一个物体都不选，由于选择的物体体积之和可能相同，我们还需要去重操作（hash）。在这道题中，我们枚举每一个物体，如果物体被选择则计算已选物体体积之和，否则直接跳过该物体，直到物体被全部枚举到。在这里我们搜索的顺序是什么呢？

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int v[N], hash[20 * 50 + 10];

void dfs(int u, int sum) {
    if(u == N) {
        hash[sum] = 1;
        return;
    }

    dfs(u + 1, sum + v[u]);
    dfs(u + 1, sum);
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> v[i];

    // 第0个物体
    dfs(0, 0);

    // 去重并计算方案数
    int cnt = 0;
        // 从1开始
    for(int i = 1; i < 12; i++) {
        if(hash[i] == 1) {
            cnt ++;
        }
    }
    cout << cnt << endl;

    return 0;
}

在以上例题中，我们可以用以下术语来描述:

  1. 状态：对问题中某些信息的描述。有起始状态、中间状态、目标状态。
  2. 规则：对状态或状态关系进行约束的条件。有产生式规则、目标判定规则、判重规则。一般是 if 语句。
    1. 产生式规则：对状态的转移进行约束的规则，如如何由起始状态生成中间状态 1，、中间状态 2、....一直到目标状态。
    2. 目标判定规则：如何判定当前状态为目标状态。
    3. 判重规则：有可能产生重复的状态，需要判重，以免浪费时间和造成死循环。 因此，在搜索问题中，我们可以从“三状态三规则”入手分析。

问题 1 中：

  1. 起始状态：0（将要搜索的第 0 件物品，选或者不选）
  2. 中间状态：s（将要搜索的第 s 件物品，选或者不选）
  3. 目标状态：n（前 n−1 件物品已经搜索完，统计结果）
  4. 产生式规则：每一件物品选还是不选，两种情况
  5. 目标判定规则：if(dep == n)
  6. 判重规则：hash[sum]=1

经典深搜问题 ​

排列组合问题 ​

组合问题 ​

AcWing 92. 递归实现指数型枚举

cpp
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> res;

void dfs(int x) {
    if (x == n + 1) {
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << " ";
        }
        cout << endl;
        return ;
    }

    dfs(x + 1);
    res.push_back(x);
    dfs(x + 1);
    res.pop_back();
}

int main() {
    cin >> n;

    dfs(1);

    return 0;
}

AcWing 93. 递归实现组合型枚举

cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> res;

void dfs(int x) {
    if (res.size() > m || res.size() + (n - x + 1) < m) return ;
    if (x == n + 1) {
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << " ";
        }
        cout << endl;
        return ;
    }

	// 为了按字典序从小到大输出，我们需要先选
    res.push_back(x);
    dfs(x + 1);
    res.pop_back();
    // 后不选
    dfs(x + 1);
}

int main() {
    cin >> n >> m;

    dfs(1);

    return 0;
}

递归实现组合型枚举的另外两种写法

cpp
int path[20];
int n, m;

// dfs(1, 1);
void dfs(int u, int start) {
    if(u > m) {
        for(int i = 1; i <= m; i++) cout << path[i] << " ";
        cout << endl;

        return;
    }

    for(int i = start; i <= n; i++) {
        path[u] = i;
        dfs(u + 1, i + 1);
        path[u] = 0; // 可省略
    }
}

// dfs(1)
void dfs(int u) {
    if(u > m) {
        for(int i = 1; i <= m; i++) cout << path[i] << " ";
        cout << endl;

        return;
    }

    for(int i = path[u - 1] + 1; i <= n; i++) {
        path[u] = i;
        dfs(u + 1);
    }
}

排列问题 ​

AcWing 94. 递归实现排列型枚举

cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 20;
int n;
int path[N];
int st[N];

void dfs(int u) {
    if(u == n + 1) {
        for(int i = 1; i <= n; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = 1; i <= n; i++) {
        if(!st[i]) {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
            path[u] = 0; // 该行可以省略
        }
    }
}

int main() {
    cin >> n;
    dfs(1);

    return 0;
}

思考：如何输出不规则数的排列和组合？

素数环 ​

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 35;
int path[N], n;
bool st[N];

bool isprime(int n) {
    int srt = (int)sqrt(n * 1.0);
    for (int i = 2; i <= srt; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

void dfs(int u) {
    if(u == n && isprime(path[0] + path[n - 1]) && path[0] == 1) {
        for(int i = 0; i < n; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = 1; i <= n; i++) {
        if(!st[i] && (u == 0 || isprime(i + path[u - 1]))) {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main() {
    cin >> n;

    dfs(0);

    return 0;
}

整数拆分 ​

DP 求拆分方案数

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int path[N], n, s;
unsigned cnt = 0;

void dfs(int u) {
    if(s == 0) {
        cnt++;
        cout << n << "=";
        for(int i = 1; i < u; i++) {
        	if(i == u - 1) cout << path[i];
        	else cout << path[i] << "+";
		}
        cout << endl;
        return ;
    }

    for(int i = path[u - 1]; i < n; i++) {
        if(i <= s) {
            path[u] = i;
            s -= i;
            dfs(u + 1);
            s += i;
        }
    }
}

int main() {
    cin >> n;

    path[0] = 1;
    s = n;
    dfs(1);

	// cout << cnt << endl;

    return 0;
}

// 把s作为参数
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int path[N], n;
unsigned cnt = 0;

void dfs(int u, int s) {
    if(s == 0) {
        cnt++;
		cout << n << "=";
        for(int i = 1; i < u; i++) {
        	if(i == u - 1) cout << path[i];
        	else cout << path[i] << "+";
		}
        cout << endl;
        return ;
    }

    for(int i = path[u - 1]; i < n; i++) {
        if(i <= s) {
            path[u] = i;
            s -= i;
            dfs(u + 1, s);
            s += i;
        }
    }
}

int main() {
    cin >> n;
    path[0] = 1;

    dfs(1, n);

    // cout << cnt << endl;

    return 0;
}

跳马迷宫问题 ​

示例 1 ​

一个迷宫，用 n∗m 的矩阵描述。每个格点有两种状态 . 或者 #，前者表示可通行，后者表示不可通行。在迷宫中，只能以上下左右四个方向移动，一次移动一格。起点为 A，出口为 B。问从起点到出口共有多少种方案？数据保证起点和出口状态都是 .。

cpp
#include <bits/stdc++.h>
using namespace std;

int dx[] = {-1, 1, 0, 0}; // 上下左右四个方向的x偏移量
int dy[] = {0, 0, -1, 1}; // 上下左右四个方向的y偏移量

int sx, sy, ex, ey;
int res = 0;
int st[4][4];


char ch[4][4] = {
    {'.', '.', '.', '.'},
    {'.', '#', '#', '.'},
    {'.', '#', '#', '.'},
    {'.', '.', '.', '.'},
};


void dfs(int x, int y) {
    for(int i = 0; i< 4; i++) {
        int x0 = x + dx[i], y0 = y + dy[i];
        if(x0 >= 0 && x0 < 4 && y0 >= 0 && y0 < 4 && !st[x0][y0] && ch[x0][y0] == '.') {
            st[x0][y0] = 1;
            if(x0 == ex && y0 == ex) res++;
            else dfs(x0, y0);
            st[x0][y0] = 0;
        }
    }
}

int main() {

    cin >> sx >> sy >> ex >> ex;

    st[sx][sy] = 1;
    dfs(sx, sy);

    cout << res << endl;

    return 0;
}
cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int n, a, b, c, d;
char g[N][N];
int st[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1,  0, -1};


bool dfs(int sx, int sy) {
    if(sx == c && sy == d) return true;

    for(int i = 0; i < 4; i++) {
        int x = sx + dx[i], y = sy + dy[i];
        if(x >= 0 && x < n && y >= 0 && y < n && g[x][y] == '.' && st[x][y] == 0) {
            st[sx][sy] = 1;
            if(dfs(x, y)) return true;
        }
    }

    return false;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; i++) cin >> g[i];

        memset(st, 0, sizeof  st);

        cin >> a >> b >> c >> d;
        if(g[a][b] == '#' || g[c][d] == '#') {
            cout << "NO" << endl;
            continue;
        }
        if(dfs(a, b)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}
cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 10;
bool st[N][N];

int n, m;
int x, y;
int res;

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

void dfs(int sx, int sy, int cnt) {
    if(cnt == n * m) {
        res++;
        return;
    }

    st[sx][sy] = true;
    for(int i = 0; i < 8; i++) {
        int a = sx + dx[i], b = sy + dy[i];
        if(a >= 0 && a < n && b >= 0 && b < m && !st[a][b]) {
            dfs(a, b, cnt + 1);
        }
    }
    st[sx][sy] = false;
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        // memset(st, false, sizeof st); // 该行可以省略，为什么？
        res = 0;

        cin >> n >> m >> x >> y;

        dfs(x, y, 1);

        cout << res << endl;
    }

    return 0;
}

红与黑 ​

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 25;
char g[N][N];
int w, h, cnt;


int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

void dfs(int x,int y)
{
    g[x][y]='#';
    cnt++;
    for(int i=0;i<4;i++)
    {
        int x1 = x + dx[i], y1 = y + dy[i];
        if(x1 < 0 || x1 >= h || y1 < 0 || y1 >= w || g[x1][y1] == '#') continue;
        dfs(x1, y1);
    }
}

int main() {
    while(cin >> w >> h, w || h) {

        for(int i = 0; i < h; i++) {
            scanf("%s", g[i]);
        }

        int x, y, flag = 0;
        for(int i = 0; i < h;i++) {
            for(int j = 0; j < w; j++)
                if(g[i][j] == '@') {
                    x = i, y = j;
                    flag = 1;
                }
            if(flag) break;
        }

        cnt = 0;
        dfs(x, y);

        cout << cnt << endl;
    }


    return 0;
}

八皇后问题 ​

n 皇后 ​

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
char g[N][N];
bool col[N], dg[N], udg[N];
int n;

void dfs(int u) {
    if(u == n) {
        for(int i = 0; i < n; i++) {
            puts(g[i]);
        }
        puts("");
        return;
    }

    for(int i = 0; i < n; i++) {
        if(!col[i] && !dg[u + i] && !udg[n - u + i]) {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
    }
}

int main() {
    cin >> n;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            g[i][j] = '.';
        }
    }

    dfs(0);

    return 0;
}

剪枝 ​

剪枝，就是减少搜索树的规模，减少搜索树中不必要的分支。常见的剪枝方法有以下几种：

  1. 优化搜索顺序
  2. 排除等效性冗余：使用组合型搜索
  3. 可行性剪枝
  4. 最优性剪枝
  5. 记忆化搜索

AcWing 165. 小猫爬山

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int cab[N], c[N], ans, n, w;

void dfs(int now, int cnt) {
    if (cnt > ans) return ; // 最优性剪枝
    if (now == n + 1) {
        ans = min(ans, cnt);
        return ;
    }

    for (int i = 1; i <= cnt; i++) {
        if (w - cab[i] >= c[now]) { // 可行性剪枝
            cab[i] += c[now];
            dfs(now + 1, cnt);
            cab[i] -= c[now];
        }
    }
    cab[cnt + 1] += c[now];
    dfs(now + 1, cnt + 1);
    cab[cnt + 1] = 0;
}

int main() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) cin >> c[i];

    // 优化搜索顺序
    sort(c + 1, c + n + 1);
    reverse(c + 1, c + n + 1);

    ans = n;
    dfs(1, 0);
    cout << ans << endl;

    return 0;
}

记忆化搜索 ​

数的计数 ​

cpp
#include <bits/stdc++.h>
using namespace std;

int res = 0;

void dfs(int m) {
	res ++;
	for(int i = 1; i <= m / 2; i++) dfs(i);
}

int main() {
	int n;
	cin >> n;

	dfs(n);

	cout << res << endl;

	return 0;
}

// 记忆化数组优化
int f[1010];

int dfs(int m) {
    if (m == 1) return 1;  // 终止条件
    if(f[m]) return f[m];

    int cnt = 1;  		// 当前数字自身也满足条件
    for (int i = 1; i <= m / 2; i++) {
        cnt += dfs(i);  // 在左边加上一个自然数
    }

    f[m] = cnt;

    return f[m];
}

切木棍 ​

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int p[N], f[N], n;

int dfs(int u) {
	if(f[u]) return f[u];
	if(u == 0) return 0;

	int maxx = -1;
	for(int i = 1; i <= u; i++) {
		maxx = max(maxx, p[i] + dfs(u - i));
	}

	f[u] = maxx;
	return f[u];
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> p[i];

	cout << dfs(n) << endl;

	return 0;
}

Copyright © 2025-present loop3r