深度优先搜索（Depth-First Search，DFS）
在计算机科学中，DFS 是一种常用的搜索算法。它的基本思想是从一个起始状态开始，尽可能深入地探索可能的状态，直到达到目标状态或无法继续前进为止。然后，回溯到上一个状态，并继续探索其他可能的路径。
DFS算法就像一个执着的人，会沿着一个方向一直搜索，直到搜索到尽头才会回头继续搜索其他方向
以下是几道DFS的入门题型：
1. 跳台阶问题
点击跳转至题目
这个示例通过递归的方式计算到达指定台阶数的不同跳法。使用了记忆化搜索来避免重复计算。
int dfs(int x)
{if (x == 1) return 1;if (x == 2) return 2;if (arr[x]) return arr[x];// 记忆化，减少递归次数 return arr[x] = dfs(x-1) + dfs(x - 2);
}
2. 指数型枚举
点击跳转至题目
这个示例枚举每个数字的选或不选情况，并通过递归构建所有可能的组合。
void dfs(int x)
{if (x > n){for (int i = 1; i <= n; i++){if (st[i])cout << i << " ";}cout << endl;return;}// 选st[x] = 1;dfs(x + 1);st[x] = 0;// 还原现场 // 不选dfs(x + 1);
}
3. 排列型枚举
点击跳转至题目
这个示例枚举每个位置可以填充的数字，并通过递归构建所有可能的排列。
void dfs(int x)
{if (x > n){for (int i = 1; i <= n; i++)cout << " " << arr[i];cout << endl;return;}// 从小到大扫描没有选的数字for (int i = 1; i <= n; i++){if (!st[i]){st[i] = 1;arr[x] = i;dfs(x + 1);st[i] = 0;// 还原现场 }}
}
4. 组合型枚举
点击跳转至题目
这个示例在给定的数字范围内，通过递归和剪枝枚举满足条件的组合。
这次的dfs函数多了一个参数start，用来记录每次从哪开始枚举，因为这次是组合型枚举，顺序不同其实是同一种，利用start来避免重复枚举
void dfs(int x,int start)
{// 剪枝if (x-1+n-start+1<r) return;if (x > r){for (int i = 1; i <= r; i++){cout << setw(3) << arr[i];// 设置场宽 }cout << endl;return;}for (int i = start; i <= n; i++){if (!st[i]){arr[x] = i;st[i] = 1;dfs(x + 1,i+1);st[i] = 0;// 还原现场 }}
}
这些代码示例都展示了 DFS 的基本思想和应用。在实际应用中，需要根据问题的特点进行适当的优化，如使用记忆化搜索、剪枝等技术，以提高算法的效率和性能。
希望这篇博客对你理解 DFS 有所帮助！如果你有任何其他问题或需要进一步的讨论，欢迎留言。
