写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
n, k （6 < n ≤ 200，2 ≤ k ≤ 6）
输出格式：
1 个整数，即不同的分法。
输入样例：
7 3
输出样例：
4
提示：
四种分法为：
1, 1, 5;
1, 2, 4;
1, 3, 3;
2, 2, 3.
解题思路：
我们使用深度优先搜索的时候，
第一个要注意的点是搜索的顺序，
因为我们要保证，
我们写出的递归结构能够遍历所有情况。
（以上递归搜索的基本思路，多熟悉总是好的）
接下来是具体思路：
我们先根据题目条件画出递归搜索树：
根节点：（以题目给出的样例为例）
从第一位置开始，我们从1开始填数字：
题目要求下一个数要大于等于前一个数，
我们发现，题目要求最大是7，而从3开始最小的和也是9，
我们就能直接判断他是不合法的，需要剪枝。
继续递归搜索：
我们发现，当1 + 4 + 4 > 7 ， 2 + 3 + 3 > 7，这两个情况之后也需要剪枝，
总结这个剪枝的规律，其实就是：
如果当前的值的总和 + 接下来剩下位置的数量 * 起始数值 > 题目要求的值，
就不用继续递归搜索了。
继续往下递归搜索：
我们就根据这个规律去实现代码即可：（记得剪枝）
代码：
//包含常用头文件 #include #include #include #include using namespace std; int n, k; //因为题目只需要返回计数，所以不用专门开一个数组记录，直接用一个变量计数即可 int res = 0; void dfs(int u, int start, int sum) { //遍历完三个位置 if(u > k) { //如果符合条件 if(sum == n) res++; return; } //如果当前的sum + 接下来剩下位置的数量 * 起始数值 > 题目要求的值，就不用继续递归搜索了 for(int i = start; sum + i * (k - u + 1) <= n; i++) { dfs(u + 1, i, sum + i); } } int main() { cin >> n >> k; dfs(1, 1, 0); printf("%d\n", res); return 0; }
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
