使用dfs加剪枝写题目“数的划分”

下面是使用深度优先搜索（DFS）加剪枝的代码实现：

#include <iostream>
using namespace std;

int n, k, all = 0;

void dfs(int sum, int step, int x)
{
    // 剪枝条件
    if (sum > n || step > k) return;
    if (sum == n && step == k) {
        ++all;
        return;
    }
    
    // 从 x 开始搜索，避免重复计算
    for (int i = x; i <= n; ++i) {
        dfs(sum + i, step + 1, i);
    }
}

int main()
{
    cin >> n >> k;
    dfs(0, 0, 1);
    cout << all << endl;
    
    return 0;
}

这里的 `dfs` 函数用于进行深度优先搜索，其中 `sum` 表示当前已经累加的数字和，`step` 表示当前的步数（即已经划分的数字个数），`x` 表示下一个搜索的起点。

在 `dfs` 函数中，我们首先进行剪枝，如果当前的数字和 `sum` 大于目标值 `n` 或者步数 `step` 大于目标划分个数 `k`，则直接返回。然后，我们判断是否达到了目标值 `n` 和目标划分个数 `k`，如果是，则将结果计数器 `all` 加一。接下来，我们从 `x` 开始进行下一轮搜索，注意避免重复计算，所以下一轮搜索的起点是 `i`。

在 `main` 函数中，我们读取输入的数值 `n` 和 `k`，然后调用 `dfs` 函数进行搜索，并输出最终的结果。

这样的实现可以通过深度优先搜索的方式枚举所有可能的划分方式，并利用剪枝策略减少不必要的搜索。