从‘放苹果’到‘整数拆分’：用C++四种解法搞定洛谷P2386和信息学奥赛经典题

1361976860

396人浏览 · 2026-06-08 14:51:29

1361976860 · 2026-06-08 14:51:29 发布

从‘放苹果’到‘整数拆分’：用C++四种解法搞定洛谷P2386和信息学奥赛经典题

在算法竞赛的进阶之路上，"放苹果"问题堪称一道经典的分水岭。这道看似简单的题目背后，隐藏着整数拆分的数学本质，以及递归、动态规划等核心算法思想的精妙应用。本文将带你从零开始，通过四种截然不同却又内在关联的解法，彻底掌握这一经典问题的求解之道。

1. 问题本质与数学建模

"放苹果"问题的标准描述是：将M个相同的苹果放入N个相同的盘子，允许有的盘子空着不放，问共有多少种不同的分法。这道题在洛谷P2386、OpenJudge以及信息学奥赛系列教材中多次出现，其重要性可见一斑。

从数学角度看，这实际上等价于 正整数拆分 问题——将整数M表示为不超过N个正整数的和，且不考虑顺序。例如，将4个苹果放入3个盘子，对应的拆分方式为：

4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1

关键观察点 ：

盘子相同意味着顺序不重要（2+1+1和1+2+1是同一种分法）
允许空盘等价于允许使用少于N个盘子
每个盘子至少放0个苹果

这个问题与《火影忍者》中的"鸣人影分身"问题（将查克拉分成若干份）完全同构，也与计算机科学中的资源分配、组合数学等问题密切相关。理解这一点，就能举一反三解决一系列相似问题。

2. 递推解法：自底向上的构建艺术

递推是解决这类计数问题的自然思路。我们定义状态 dp[i][j] 表示将i个苹果放入j个盘子的方案数，然后寻找状态转移关系。

2.1 状态转移分析

递推关系的建立需要考虑以下几种情况：

边界条件 ：
- 0个苹果：只有一种分法（所有盘子空着）→ dp[0][j] = 1
- 1个盘子：只有一种分法（所有苹果放入该盘子）→ dp[i][1] = 1
- 苹果数≤盘子数：等价于每个盘子最多放1个苹果→ dp[i][j] = dp[i][i]
一般情况 （i>j）：
- 至少有一个盘子空着： dp[i][j-1]
- 所有盘子都有至少一个苹果：先在每个盘子放1个苹果，剩余i-j个苹果自由分配→ dp[i-j][j]

因此，完整的递推式为：

dp[i][j] = dp[i][j-1] + (i >= j ? dp[i-j][j] : 0);

2.2 代码实现与优化

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, m, n, dp[15][15] = {};
    
    // 预处理所有可能的状态
    for(int i = 0; i <= 10; ++i) 
        for(int j = 1; j <= 10; ++j) {
            if(i == 0 || j == 1) dp[i][j] = 1;
            else if(i < j) dp[i][j] = dp[i][i];
            else dp[i][j] = dp[i][j-1] + dp[i-j][j];
        }
    
    cin >> t;
    while(t--) {
        cin >> m >> n;
        cout << dp[m][n] << endl;
    }
    return 0;
}

性能分析 ：

时间复杂度：O(M*N)预处理，O(1)查询
空间复杂度：O(M*N)
适用于多组查询场景，是竞赛中的首选方法

3. 递归解法：分而治之的思维训练

递归解法直接模拟问题定义，将大问题分解为小问题，是理解问题本质的最佳途径。

3.1 递归关系设计

递归函数 solve(i,j) 表示将i个苹果放入j个盘子的方案数，其逻辑与递推完全对应：

int solve(int i, int j) {
    if(i == 0 || j == 1) return 1;  // 边界条件
    if(i < j) return solve(i, i);    // 苹果不足
    return solve(i, j-1) + solve(i-j, j); // 一般情况
}

3.2 记忆化优化

原始递归存在大量重复计算，通过记忆化可以大幅提升效率：

#include <bits/stdc++.h>
using namespace std;

int memo[15][15]; // 记忆化数组

int solve(int i, int j) {
    if(memo[i][j]) return memo[i][j];
    if(i == 0 || j == 1) return memo[i][j] = 1;
    if(i < j) return memo[i][j] = solve(i, i);
    return memo[i][j] = solve(i, j-1) + solve(i-j, j);
}

int main() {
    int t, m, n;
    cin >> t;
    while(t--) {
        cin >> m >> n;
        cout << solve(m, n) << endl;
    }
    return 0;
}

对比分析 ：

方法	时间复杂度	空间复杂度	适用场景
普通递归	O(2^(M+N))	O(M+N)	教学理解
记忆化递归	O(M*N)	O(M*N)	单次查询
递推	O(M*N)预处理	O(M*N)	多次查询

4. DFS解法：暴力搜索的优雅实践

深度优先搜索(DFS)提供了一种直观的暴力解法，虽然效率不高，但对训练搜索思维很有帮助。

4.1 搜索策略设计

关键点在于避免重复计数。我们规定拆分序列为非递减排列，即后一个数不小于前一个数：

void dfs(int remain, int start, int depth) {
    if(depth == n) {
        if(remain == 0) ans++;
        return;
    }
    for(int i = start; i <= remain; ++i)
        dfs(remain - i, i, depth + 1);
}

4.2 完整实现与剪枝

#include <bits/stdc++.h>
using namespace std;

int m, n, ans;

void dfs(int remain, int start, int depth) {
    if(remain == 0 && depth <= n) {
        ans++;
        return;
    }
    if(depth >= n) return;
    
    for(int i = start; i <= remain; ++i)
        dfs(remain - i, i, depth + 1);
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> m >> n;
        ans = 0;
        dfs(m, 1, 0);
        cout << ans << endl;
    }
    return 0;
}

优化技巧 ：

提前终止：当剩余苹果为0时立即计数
层级控制：确保拆分次数不超过n次
起始值递增：保证序列非递减

5. 动态规划：通用框架的经典应用

虽然递推解法已经体现了DP思想，但用标准的DP框架重新分析，可以加深对状态设计的理解。

5.1 状态定义与转移

定义 dp[k][i][j] 表示前k个盘子放i个苹果且第k个盘子至少放j个的方案数。经过优化可简化为二维：

dp[i][j] = dp[i][j-1] + dp[i-j][j]

这与递推式一致，但思考角度不同：将问题看作 完全背包问题 ，其中盘子是"物品"，苹果是"容量"，每个盘子可以重复使用。

5.2 空间优化技巧

可以进一步优化为一维数组：

int dp[15] = {1}; // dp[0] = 1

for(int j = 1; j <= n; ++j)
    for(int i = j; i <= m; ++i)
        dp[i] += dp[i-j];

不过对于竞赛题目，二维数组通常已经足够。

6. 实战对比与选择指南

四种解法各有特点，适用于不同场景：

教学演示 ：递归 > DFS > 递推 > DP
竞赛编程 ：递推 > 记忆化递归 > DP > DFS
思维训练 ：DFS > 递归 > DP > 递推

重要参数对比 ：

方法	代码复杂度	时间复杂度	空间复杂度	扩展性
递推	★★☆☆☆	O(M*N)	O(M*N)	易于优化
递归	★★★☆☆	O(2^N)	O(N)	不易并行
记忆化递归	★★★★☆	O(M*N)	O(M*N)	需管理状态
DFS	★★★★★	O(指数级)	O(N)	剪枝灵活
DP	★★☆☆☆	O(M*N)	O(M*N)	框架通用