算法刷题【洛谷P1025 & NOIP2001 提高组】数的划分（排列组合解法）

# 题目描述

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：$n=7$，$k=3$，下面三种分法被认为是相同的。

$1,1,5$; $1,5,1$; $5,1,1$.

问有多少种不同的分法。

# 输入格式

$n,k$ （$n \le 200$，$2 \le k \le 6$）

# 输出格式

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

# 输入输出样例

In 1

7 3

Out 1

4

# 说明/提示

四种分法为：
$1,1,5$;
$1,2,4$;
$1,3,3$;
$2,2,3$.

【题目来源】

NOIP 2001 提高组第二题

这道题的数据范围吧其实dfs暴力能过

但是为了方便起见

（我不会dfs）

就来一个排列组合的解法

仔细读题你会发现这貌似就是个苹果分盘子 不允许有空的经典问题！

具体的在注释里面了

#include <iostream>
using namespace std;

int dfs(int n, int k) {
    // 用k个数组成n，即把n分成k份
    if (n < k)  // 由于不能有0，所以n无法分成k（k > n）份
        return 0;
    else if (n == k || k == 1)  // 每组都是1或只有1组，无需继续递归
        return 1;
    else
        return dfs(n - 1, k - 1) + dfs(n - k, k);
        // k个数至少一个为1的方案数 + 全部不为1的方案数（见下方文字详解）
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << dfs(n, k);

    return 0;
}

有关 dfs(n, k) = dfs(n - 1, k - 1) + dfs(n - k, k) 的详细解释：

• dfs(n - 1, k - 1)：在k个组成n的数中至少有1个数字是1，则我们把这一个数字删掉，结果相同。
• dfs(n - k, k)：在k个组成n的数中没有数字是1，则在各个部分减去1。随便举个例子，自己简单证明一下易得：3个数字组成数字7的不含数字1的方案数 等于 3个数字组成数字7-3=4的所有方案数

代码简单到懒得用万能头，思路咋说呢，本来写完觉得还可以，昨天在一个读者询问下整不会了又仔细想了想才给回复，所以大家还是要记得时常复习！（2021.12.14补）