整数无序分拆 – ViTe 小宇宙

1. 问题形式化定义

1.1 题目原描述

将 $M$ 个相同的苹果放入 $N$ 个相同的盘子中，允许盘子为空，不区分盘子的顺序（如分拆 $[5,1,1]$ 与 $[1,5,1]$ 视为同一种），求不同的分法总数 $K$ 。

1.2 数学建模

该问题等价于组合数学中的整数无序分拆问题：

给定非负整数 $M$ （被分拆数）与正整数 $N$ （分拆的最大部分数），求将 $M$ 分拆为至多 $N$ 个非负整数的无序分拆的数目。其中，分拆的任意排列视为同一个分拆，仅由元素的多重集合决定。

为简化分析，定义核心计数函数：

$f(m,n) = \text{将 } m \text{ 个苹果放入 } n \text{ 个相同盘子的分法总数}$

我们的目标是对给定的 $M,N$ ，计算 $f(M,N)$ 。

2. 核心原理：无序分拆的去重与双射证明

无序分拆的核心难点是避免重复计数，其本质是消除排列带来的冗余。我们通过以下定理解决该问题：

定理1：无序分拆与非递增序列的一一对应

任意一个将 $m$ 分拆为至多 $n$ 个非负整数的无序分拆，唯一对应一个长度为 $n$ 的非递增非负整数序列；反之，任意一个长度为 $n$ 的非递增非负整数序列，唯一对应一个无序分拆。

证明

正向映射：对任意无序分拆，将其元素按非递增顺序排序，补0至长度为 $n$ ，得到唯一的非递增序列。
反向映射：对任意长度为 $n$ 的非递增非负整数序列，其元素的多重集合唯一对应一个无序分拆。
该映射为双射（一一对应），因此对无序分拆的计数，等价于对满足条件的非递增序列的计数。

该定理是所有解法的核心基础：通过强制序列非递增，从根源上消除排列带来的重复计数，保证计数的不重不漏。

3. 解法一：暴力DFS枚举法（模拟法）

3.1 算法思路

基于定理1，通过深度优先搜索（DFS）递归构造满足以下条件的非递增序列：

序列长度为 $N$ （盘子总数）；
序列元素非递增（后一个元素 ≤ 前一个元素）；
序列元素之和为 $M$ （苹果总数）。

递归函数定义为：

$dfs(rest, last, idx) = \text{剩余 } rest \text{ 个苹果，当前盘子最多放 } last \text{ 个，正在放第 } idx \text{ 个盘子的分法数}$

3.2 正确性证明

由定理1，所有合法分拆与满足条件的非递增序列一一对应。DFS枚举了所有满足非递增约束、和为 $M$ 的长度为 $N$ 的序列，因此计数结果不重不漏，与 $f(M,N)$ 等价。

3.3 复杂度分析

时间复杂度：指数级 $O(e^{\pi\sqrt{2M/3}})$ ，与整数分拆数的渐近增长一致。递归过程无缓存，存在大量重复子问题计算，仅能处理 $M,N \leq 15$ 的极小数据。
空间复杂度： $O(N)$ ，为递归栈的深度（最多递归 $N$ 层）。

4. 解法二：记忆化搜索法

4.1 递推关系的严谨推导与证明

我们通过分情况讨论，推导 $f(m,n)$ 的递推关系，并通过双射证明其正确性。

4.1.1 边界条件

当 $m=0$ 时：仅存在1种分法（所有盘子为空），因此 $f(0,n)=1, \forall n \geq 0$ 。
当 $n=0$ 时：仅当 $m=0$ 时有1种分法，否则无法放置，因此 $f(m,0)=0, \forall m > 0$ 。

4.1.2 核心递推式

情况1： $n > m$ （盘子数 > 苹果数）

此时有 $f(m,n) = f(m,m)$ 。

证明

设 $S$ 为 $m$ 个苹果放入 $n$ 个盘子的分拆集合， $T$ 为 $m$ 个苹果放入 $m$ 个盘子的分拆集合。

对任意分拆 $s \in S$ ，因 $m < n$ ，序列中至少有 $n-m$ 个0，去掉末尾的 $n-m$ 个0，得到长度为 $m$ 的非递增序列 $s' \in T$ 。
对任意分拆 $s' \in T$ ，在末尾补 $n-m$ 个0，得到长度为 $n$ 的非递增序列 $s \in S$ 。

该映射为双射，因此 $|S|=|T|$ ，即 $f(m,n)=f(m,m)$ 。

情况2： $n \leq m$ （盘子数 ≤ 苹果数）

此时有 $f(m,n) = f(m,n-1) + f(m-n,n)$ 。

证明

将所有分拆划分为两个不交的子集：

子集A：至少有1个盘子为空

去掉1个空盘子，分拆与「 $m$ 个苹果放入 $n-1$ 个盘子」的分拆一一对应，因此 $|A|=f(m,n-1)$ 。

子集B：所有盘子非空（每个盘子至少1个苹果）

给每个盘子先放1个苹果，剩余 $m-n$ 个苹果，分拆与「 $m-n$ 个苹果放入 $n$ 个盘子」的分拆一一对应，因此 $|B|=f(m-n,n)$ 。

因 $A \cup B$ 为全集，且 $A \cap B = \emptyset$ ，故 $f(m,n)=|A|+|B|=f(m,n-1)+f(m-n,n)$ 。

4.2 算法实现思路

在纯递归的基础上，引入二维缓存数组 memo[m][n]，记录已经计算过的 $f(m,n)$ ，避免重复子问题的计算。递归时若 memo[m][n] 已计算，直接返回缓存值，否则计算后存入缓存。

4.3 复杂度分析

时间复杂度：多项式级 $O(M \times N)$ 。状态总数为 $(M+1) \times (N+1)$ ，每个状态仅计算1次，每次计算的时间复杂度为 $O(1)$ 。
空间复杂度： $O(M \times N)$ ，为缓存数组的空间开销，叠加 $O(N)$ 的递归栈开销。

5. 解法三：动态规划（DP）迭代法

5.1 算法思路与填表逻辑

动态规划是记忆化搜索的迭代实现，通过自底向上的方式填充DP表，避免递归栈开销。

DP数组定义：dp[i][j] = f(i,j)，即 $i$ 个苹果放入 $j$ 个盘子的分法总数。
初始化：按边界条件初始化DP表：
- dp[0][j] = 1，对所有 $0 \leq j \leq N$ ；
- dp[i][1] = 1，对所有 $0 \leq i \leq M$ 。
填表顺序：按苹果数 $i$ 从1到 $M$ 递增，盘子数 $j$ 从2到 $N$ 递增，保证计算 dp[i][j] 时，其依赖的 dp[i][j-1] 和 dp[i-j][j] 已完成计算。
状态转移：

dp[i][j] = \begin{cases} dp[i][i] & j > i \ dp[i][j-1] + dp[i-j][j] & j \leq i \end{cases}

5.2 正确性证明

DP表的填充完全遵循4.1节中严格证明的递推关系与边界条件，自底向上的计算顺序保证了所有依赖状态的提前求解，因此最终 dp[M][N] 与 $f(M,N)$ 完全等价。

5.3 复杂度分析

时间复杂度：多项式级 $O(M \times N)$ ，与记忆化搜索一致，无递归常数开销，实际运行效率更高。
空间复杂度： $O(M \times N)$ ，可通过滚动数组优化至 $O(M)$ ，基础实现无需优化即可满足题目约束。

6. 三种解法的综合对比

解法	时间复杂度	空间复杂度	核心优势	核心缺陷	适用场景
暴力DFS枚举	指数级	$O(N)$	逻辑直观，完全贴合分拆的构造过程，易理解	时间复杂度过高，仅能处理极小数据	算法入门教学，分拆原理演示
记忆化搜索	$O(M \times N)$	$O(M \times N)$	兼顾递归的可读性与多项式级效率，代码易写	存在递归栈溢出风险，递归调用有常数开销	竞赛快速实现，原理过渡学习
动态规划迭代	$O(M \times N)$	$O(M \times N)$	效率最高，无递归风险，是该问题的标准解法	需提前理解状态转移方程，对新手直观性较弱	正式考试/竞赛，工程化实现

7. 问题变体与拓展

盘子不允许为空：等价于将 $M$ 分拆为恰好 $N$ 个正整数的分拆数，结果为 $f(M-N, N)$ （先给每个盘子放1个苹果，剩余 $M-N$ 个自由分拆）。
盘子可区分：等价于可重组合问题，用隔板法求解，结果为 $\binom{M+N-1}{N-1}$ ，与无序分拆的核心区别是排列视为不同分拆。
生成函数表示： $f(M,N)$ 是生成函数 $F(x) = \prod_{k=1}^N \frac{1}{1-x^k}$ 展开后 $x^M$ 项的系数，该结论是整数分拆的核心生成函数理论。

8. 标准代码实现

8.1 暴力DFS枚举法


#include <iostream>
#include <algorithm>
using namespace std;

int dfs(int rest, int last, int idx, int total_plate) {
    if (idx == total_plate) return rest == 0 ? 1 : 0;
    int count = 0;
    for (int i = 0; i <= min(last, rest); ++i) {
        count += dfs(rest - i, i, idx + 1, total_plate);
    }
    return count;
}

int main() {
    int t, M, N;
    cin >> t;
    while (t--) {
        cin >> M >> N;
        cout << dfs(M, M, 0, N) << endl;
    }
    return 0;
}

8.2 记忆化搜索法


#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 15;
int memo[MAX][MAX];

int f(int m, int n) {
    if (m == 0) return 1;
    if (n == 0) return 0;
    if (memo[m][n] != -1) return memo[m][n];
    int res;
    if (n > m) res = f(m, m);
    else res = f(m, n-1) + f(m - n, n);
    return memo[m][n] = res;
}

int main() {
    memset(memo, -1, sizeof(memo));
    int t, M, N;
    cin >> t;
    while (t--) {
        cin >> M >> N;
        cout << f(M, N) << endl;
    }
    return 0;
}

8.3 动态规划迭代法


#include <iostream>
using namespace std;

const int MAX = 15;
int dp[MAX][MAX];

void init_dp() {
    for (int j = 0; j < MAX; ++j) dp[0][j] = 1;
    for (int i = 0; i < MAX; ++i) dp[i][1] = 1;
    for (int i = 1; i < MAX; ++i) {
        for (int j = 2; j < MAX; ++j) {
            if (j > i) dp[i][j] = dp[i][i];
            else dp[i][j] = dp[i][j-1] + dp[i-j][j];
        }
    }
}

int main() {
    init_dp();
    int t, M, N;
    cin >> t;
    while (t--) {
        cin >> M >> N;
        cout << dp[M][N] << endl;
    }
    return 0;
}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31