从‘放苹果’到‘整数拆分’：用四种解法搞定NOI/洛谷经典递推题（附C++代码）

在算法竞赛的进阶之路上， "放苹果"问题 堪称一块绝佳的试金石。这道看似简单的题目，却能衍生出递推、递归、深搜、动态规划四种截然不同的解法，完美展现了算法思维的多面性。对于正在备战NOI/NOIP或刷题提升的中学生/大学生而言，掌握这道题的多种解法，远比单纯AC更有价值——它能帮你建立起不同算法范式间的思维桥梁。

1. 问题本质与数学建模

放苹果问题 的官方描述是：将M个相同的苹果放入N个相同的盘子，允许有的盘子空着不放，问共有多少种不同的分法。这道题在数学上等价于**"整数拆分"问题**——将一个正整数M拆分成不超过N个正整数的和，且拆分顺序无关。

举个例子，将4个苹果放入2个盘子，有3种分法：

• (3,1)
• (2,2)
• (4,0)

理解这个问题的关键在于抓住两个 核心特征 ：

1. 元素相同性 ：苹果和盘子都是不可区分的，因此(1,3)和(3,1)视为同一种分法
2. 空盘允许 ：允许部分盘子为空，这与某些变体问题（如要求每个盘子至少一个苹果）形成对比

2. 递推解法：自底向上的思维艺术

递推是解决这类组合问题的经典方法，其核心在于 定义状态和建立状态转移方程 。

2.1 状态定义

设 dp[m][n] 表示将m个苹果放入n个盘子的方案数。我们需要考虑两种基本情况：

• 边界条件 ：
  • dp[0][n] = 1 ：0个苹果只有一种分法（所有盘子为空）
  • dp[m][1] = 1 ：1个盘子时只有一种分法

2.2 状态转移

关键递推关系分为两种情况：

1. 至少一个盘子为空 ：方案数等于 dp[m][n-1]
2. 所有盘子都有苹果 ：先在每个盘子放1个苹果，剩余 m-n 个苹果继续分配，方案数为 dp[m-n][n]

因此完整的状态转移方程为：

if (m < n) 
    dp[m][n] = dp[m][m];
else
    dp[m][n] = dp[m][n-1] + dp[m-n][n];

2.3 完整实现代码

#include <iostream>
using namespace std;

int main() {
    int t, m, n, dp[15][15] = {0};
    cin >> t;
    
    // 预处理所有可能状态
    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];
        }
    }
    
    while (t--) {
        cin >> m >> n;
        cout << dp[m][n] << endl;
    }
    return 0;
}

3. 递归解法：自顶向下的分治策略

递归解法与递推思路同源，但采用了 分治思想 ，将大问题分解为子问题。

3.1 递归关系设计

定义递归函数 solve(m,n) ：

• 基准情况 ：
  • m == 0 ：返回1
  • n == 1 ：返回1
• 递归情况 ：
  • 当 m < n 时，等价于 solve(m,m)
  • 否则，返回 solve(m,n-1) + solve(m-n,n)

3.2 记忆化优化

原始递归存在大量重复计算，可通过 记忆化技术 优化：

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

int memo[15][15];

int solve(int m, int n) {
    if (memo[m][n] != -1)
        return memo[m][n];
    
    if (m == 0 || n == 1)
        return memo[m][n] = 1;
    
    if (m < n)
        return memo[m][n] = solve(m, m);
    else
        return memo[m][n] = solve(m, n-1) + solve(m-n, n);
}

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

4. 深度优先搜索：暴力美学的优雅实践

DFS解法将问题转化为 生成所有可能的拆分序列 ，需要特别注意避免重复计数。

4.1 搜索策略设计

关键点在于 保持序列非递减 ：

1. 从start开始尝试放置苹果
2. 每次放置的数量不小于前一次
3. 累计放置数量不超过盘子数n

4.2 实现细节

#include <iostream>
using namespace std;

int m, n, ans;

void dfs(int remaining, int start, int depth) {
    if (depth > n) return;
    if (remaining == 0) {
        ans++;
        return;
    }
    
    for (int i = start; i <= remaining; ++i) {
        dfs(remaining - 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;
}

5. 动态规划：递推的进阶视角

虽然递推和DP本质相通，但DP更强调 最优子结构 和 无后效性 的思考方式。

5.1 状态重新定义

设 dp[k][s] 表示用前k个盘子放置s个苹果的方案数，状态转移分为：

• 不使用第k个盘子： dp[k-1][s]
• 使用第k个盘子： dp[k][s-k]

5.2 空间优化实现

#include <iostream>
using namespace std;

int main() {
    int t, m, n, dp[15][15] = {0};
    cin >> t;
    
    while (t--) {
        cin >> m >> n;
        fill(&dp[0][0], &dp[0][0]+15*15, 0);
        dp[0][0] = 1;
        
        for (int k = 1; k <= n; ++k) {
            for (int s = 0; s <= m; ++s) {
                dp[k][s] = dp[k-1][s];
                if (s >= k)
                    dp[k][s] += dp[k][s-k];
            }
        }
        
        cout << dp[n][m] << endl;
    }
    return 0;
}

6. 方法对比与实战选择

方法	时间复杂度	空间复杂度	适用场景
递推	O(M*N)	O(M*N)	多组查询，预处理场景
递归	指数级(无记忆化)	O(M*N)	教学理解，小规模数据
DFS	O(2^M)	O(N)	需要所有具体解的场景
动态规划	O(M*N)	O(M*N)	强调最优子结构的教学

在实际比赛中：

• 推荐递推解法 ：效率最高，代码简洁
• 对特别大的M和N(如M,N>100)，可能需要更优化的DP方案
• DFS适用于需要输出所有具体分法的变体题目