苹果放盘子问题C++实现：动态规划与记忆化递归详解

## 🍎 问题分析：苹果放盘子（组合计数） 这是一个**经典动态规划/递归**问题，核心是**无序组合**（即顺序无关）。我用 **C++** 实现。 --- ### 🧠 核心思路 设 `f(m, n)` 表示 **m 个苹果放 n 个盘子** 的方法数（允许空盘）。 **递推关系**： - 如果 `m == 0` 或 `n == 1` → 只有 **1** 种方法（无苹果或只有一个盘子）。 - 如果 `m < n` → 空盘至少 `n-m` 个，等价于 `f(m, m)`（去掉空盘）。 - 否则： - **至少一个盘子空着**：`f(m, n-1)` - **每个盘子至少放 1 个苹果**：`f(m-n, n)` 所以递推式： ``` f(m, n) = f(m, n-1) + f(m-n, n) （当 m >= n） ``` --- ### 💻 C++ 实现（动态规划 + 记忆化） ```cpp #include <iostream> #include <cstring> using namespace std; const int MAX = 15; // 题目 m, n 一般很小，可调整 int dp[MAX][MAX]; // 记忆化递归 int f(int m, int n) { // 边界条件 if (m == 0 || n == 1) return 1; // 已计算过 if (dp[m][n] != -1) return dp[m][n]; if (m < n) { // 盘子比苹果多，空盘忽略 dp[m][n] = f(m, m); } else { // 至少一个空盘 + 每个盘子至少放一个 dp[m][n] = f(m, n - 1) + f(m - n, n); } return dp[m][n]; } int main() { int t; cin >> t; while (t--) { int m, n; cin >> m >> n; memset(dp, -1, sizeof(dp)); // 重置记忆化数组 cout << f(m, n) << endl; } return 0; } ``` --- ### 📊 复杂度分析 | 方法 | 时间复杂度 | 空间复杂度 | |------|------------|------------| | 递归+记忆化 | O(m*n) | O(m*n) | | 纯递归（不推荐） | 指数级 | O(深度) | | 动态规划（自底向上） | O(m*n) | O(m) 可优化 | **建议**：由于 m, n 通常 ≤ 10~15，直接用记忆化递归即可。 --- ### 🧪 测试样例 **输入**： ``` 2 7 3 5 5 ``` **输出**： ``` 8 7 ``` **解释**（7,3）： - 7=7, 6+1, 5+2, 5+1+1, 4+3, 4+2+1, 3+3+1, 3+2+2 → 共8种。 --- ### ⚠️ 易错点与开发建议 1. **边界条件务必处理**：`m==0` 和 `n==1` 必须返回1，否则递归死循环。 2. **记忆化数组初始化**：使用 `memset(dp, -1, sizeof(dp))`，每次测试重置。 3. **输入规模**：如果 m, n 可能很大（>100），需改用**动态规划二维数组**或**滚动数组**优化空间。 4. **题目提示**：`5,1,1` 和 `1,1,5` 相同，所以不能简单枚举排列，必须用组合计数方法。 --- ### 📚 扩展阅读 - [洛谷 P1025 数的划分](https://www.luogu.com.cn/problem/P1025)（类似思想） - [苹果放盘子 - 博客园详解](https://www.cnblogs.com/dongsheng/archive/2012/08/15/2640451.html) --- ######[AI写代码神器 | 948点数解答 | 2026-07-31 19:52:15]