题目描述：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种放法？ **常见技术问题：** 如何用递归或动态规划计算苹果和盘子的组合数？

Question

**题目：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种放法？** **技术问题：如何用递归或动态规划计算苹果和盘子的组合数？** 解决该问题的关键在于理解“同样的苹果”和“同样的盘子”的含义。递归方法可以通过将问题分解为子问题实现：如果盘子数N大于苹果数M，则最多只能使用M个盘子；否则，考虑当前盘子是否为空，分别递归计算放置和不放置的情况。 动态规划则通过构建二维数组dp[i][j]表示i个苹果放入j个盘子的组合数。状态转移方程为： `dp[i][j] = dp[i][j-1] + dp[i-j][j]` 其中，`dp[i][j-1]`表示至少一个盘子为空，`dp[i-j][j]`表示每个盘子至少有一个苹果。 边界条件包括：`dp[0][j]=1`（无苹果只有一种放法）和`dp[i][0]=0`（无盘子无法放置）。此方法时间复杂度为O(MN)，适合大规模计算。