数的划分 题解

第一种方法 dfs+剪枝

#include <iostream>
using namespace std;
int n, k, cnt;
void dfs(int last, int sum, int cur)
{
    if (cur == k)
    {
        if (sum == n)
            cnt++;
        return;
    }
    for (int i = last; sum + i * (k - cur) <= n; i++)
    {
        dfs(i, sum + i, cur + 1);
    }
}
int main()
{
    cin >> n >> k;
    dfs(1, 0, 0);
    cout << cnt;
}

我考虑了将整数 n 分成 k 份的所有可能情况，使用递归的方式遍历所有的分法。同时，我还使用了剪枝操作，只在满足一定条件下继续递归，从而避免了不必要的计算。不过这种递归方式在搜索大数据时能会导致栈溢出，必要时候可以使用动态规划。
可能有人会问sum+i*(k-cur)<=n这是什么意思？
sum 表示已经分配的数字之和，i 表示当前将要分配的数字，k 表示需要分成的份数，cur 表示当前正在分配的第几份。
假设我们已经分配了 cur 份数字，而还剩下 k - cur 份数字需要分配。由于每份数字不能为空，所以最小的数字为 1。因此，剩余的数字总和的最小值为 1 * (k - cur)。
现在，如果我们将当前将要分配的数字 i 加到已经分配的数字之和 sum 上，那么剩余的数字总和为 sum + i * (k - cur)。
如果 sum + i * (k - cur) 大于等于目标数字 n，那么说明即使后面的数字都是最小的情况下，我们已经超过了或达到了目标 n，因此没有必要继续分配更大的数字了，可以停止递归，这就是剪枝的目的。

第二种方法 动态规划(DP)

另一种方法是使用动态规划（DP），它可以在处理大数据时更为稳定。动态规划的思想是将大问题分解成小问题，并存储已经计算过的中间结果，避免重复计算。

#include<bits/stdc++.h>
using namespace std;
int n,k,f[201][7];  //f[k][x] k 分成 x 份 ={f[k-1][x-1],f[k-x][x]}
int main(){
    cin >> n >> k;
    for (int i=1;i<=n;i++) {f[i][1]=1;f[i][0]=1;}for (int x=2;x<=k;x++) {f[1][x]=0;f[0][x]=0;}  // 边界，为了防止炸，我把有0的也处理了
    for (int i=2;i<=n;i++)
        for (int x=2;x<=k;x++)
            if (i>x) f[i][x]=f[i-1][x-1]+f[i-x][x];
            else f[i][x]=f[i-1][x-1];
    cout<<f[n][k];
    return 0;
}

欢迎加入团队