C++实现相同物品放入相同盒子（整数划分）的计数方案

好的，这是一个经典的“整数划分”或“组合数学”问题。具体来说，它是**将 m 个相同的物品放入 n 个相同的盒子中，允许盒子为空**的方案数。这与将整数 m 拆分成不超过 n 个部分（每个部分非负）的方案数等价。 下面我将为你提供完整的 C++ 解答，并附上详细解释。 ## 🧠 问题分析 - **物品相同**：炮弹相同，因此 (5,1,1) 和 (1,1,5) 视为同一方案。 - **盒子相同**：炮口相同，因此不存在顺序区别。 - **允许空盒**：炮口可以空着不装。 这本质上是 **“整数划分”** 问题的一个变种： - 将整数 m 划分为最多 n 个正整数之和的方案数。 或者等价地：将整数 m 划分为恰好 k (0 <= k <= n) 个正整数之和的方案数，再求和。 动态规划是解决这类问题的常用方法。 ## 🚀 动态规划解法 ### 状态定义 设 `dp[i][j]` 表示 **将 i 个相同的炮弹放入 j 个相同的炮口中，允许空盒** 的方案数。 ### 递推关系 考虑最后一个炮口的装填情况： 1. **所有炮口都非空**：此时每个炮口先放 1 个炮弹，剩下的 `i - j` 个炮弹放入 j 个炮口（此时仍允许某些炮口为空）。方案数为 `dp[i - j][j]`。 2. **至少有一个炮口为空**：这意味着实际上只用了 `j - 1` 个炮口。方案数为 `dp[i][j - 1]`。 递推公式为： ``` dp[i][j] = dp[i][j - 1] + (i >= j ? dp[i - j][j] : 0) ``` ### 初始条件 - `dp[0][j] = 1`：0 个炮弹放入任何数量的炮口，只有全空 1 种方案。 - `dp[i][1] = 1`：任何数量的炮弹放进 1 个炮口，只有 1 种方案。 ### 最终答案 `dp[m][n]` 即为所求结果。 ## 💻 C++ 完整代码 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int m, n; cin >> m >> n; // dp[i][j] 表示 i 个炮弹放入 j 个炮口的方案数 // 使用 vector 动态初始化 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 边界条件：0个炮弹放入任意数量的炮口，只有1种方案 for (int j = 0; j <= n; ++j) { dp[0][j] = 1; } // 边界条件：任意数量炮弹放入1个炮口，只有1种方案 for (int i = 0; i <= m; ++i) { dp[i][1] = 1; } // 开始动态规划 for (int i = 1; i <= m; ++i) { for (int j = 2; j <= n; ++j) { // 情况1：至少有一个炮口为空 → 相当于只用 j-1 个炮口 dp[i][j] = dp[i][j - 1]; // 情况2：每个炮口至少有一个 → 先放下1个，剩下的 i-j 个放到 j 个炮口 if (i >= j) { dp[i][j] += dp[i - j][j]; } } } cout << dp[m][n] << endl; return 0; } ``` ## 📝 代码解释 - **vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));** 创建 `(m+1) x (n+1)` 的二维表，初始化为 0。 - **dp[0][j] = 1** 0 个炮弹放入 j 个炮口，方案数总是 1（全空）。 - **dp[i][1] = 1** i 个炮弹放入 1 个炮口，方案数总是 1。 - **核心递推** `dp[i][j] = dp[i][j-1] + (i >= j ? dp[i-j][j] : 0)` 理解这个公式是解题关键： - `dp[i][j-1]`：至少有一个炮口是空的。 - `dp[i-j][j]`：所有炮口都非空，每个先放 1 个，剩下的再分配。 ## 🧪 测试样例验证 ### 样例1: m=7, n=3 - 应输出 8 - 手动验证： 7 = 7 7 = 6 + 1 7 = 5 + 2 7 = 5 + 1 + 1 7 = 4 + 3 7 = 4 + 2 + 1 7 = 3 + 3 + 1 7 = 3 + 2 + 2 共8种，正确。 ### 样例2: m=4, n=3 - 应输出 4 - 手动验证： 4 3 + 1 2 + 2 2 + 1 + 1 共4种，正确。 ## 💡 开发建议 1. **整数范围较小**：题目限制 m,n ≤ 10，可以直接使用 int，不必担心溢出。 2. **可扩展性**：若 m,n 更大，注意使用 `long long` 或高精度，因为方案数会快速增长。 3. **递归 + 记忆化**：本题也可用递归实现，但动态规划的直接性和效率更优。 4. **理解实质**：这类问题核心是 **“整数划分”** ，建议学习相关数论知识（如欧拉五边形数定理）拓展思路。 ######[AI写代码神器 | 1388点数解答 | 2026-07-24 20:03:43]