写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

n, k （6 < n ≤ 200，2 ≤ k ≤ 6）

输出格式：

1 个整数，即不同的分法。

输入样例：

7 3

输出样例：

提示：

四种分法为：
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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

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;
}