牛客网 HJ61 放苹果

牛客网 HJ61 放苹果

题目链接：https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf

一、原题完整陈述

题目描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

重点：苹果相同、盘子相同。所以顺序无关。
例如7个苹果3个盘子：(5,1,1)和(1,5,1)视作同一种方案，不能重复计数

输入描述

输入两个整数 m（苹果数量）、n（盘子数量）
数据范围：0≤m≤10，1≤n≤100 \le m \le 10，1 \le n \le 100≤m≤10，1≤n≤10

输出描述

输出分法总数，int整数

样例输入

7 3

样例输出

8

全部8种方案：
(7,0,0)、(6,1,0)、(5,2,0)、(5,1,1)、(4,3,0)、(4,2,1)、(3,3,1)、(3,2,2)

二、费曼学习法拆解破解思路（讲给小白）

费曼思路：抛开术语，假装给完全不懂递归、组合数学的同学讲明白。

翻译成人话

苹果长得一模一样，盘子长得一模一样，盘子可以空。
只关心每个盘子放几个，不关心哪个盘子放，调换盘子顺序不算新方案。
我们需要算出一共有多少种分配方案。

定义函数f(m,n)：m个苹果，n个盘子，一共有多少分法

4种情况讨论

1. 边界出口1：没有苹果 m=0
   没有苹果，所有盘子全空。只有1种方法，啥都不放。f(0,n)=1

2. 边界出口2：只有1个盘子 n=1
   所有苹果只能丢进这唯一盘子，只有1种放法。f(m,1)=1

3. 盘子数量 > 苹果数量（n>m）
   盘子比苹果多，必定有n-m个盘子是空的。空盘子不影响方案种类，多余盘子直接忽略。
   等价于把m个苹果放到m个盘子。f(m,n)=f(m,m)

例：3个苹果，5个盘子，等价3苹果放3盘子，剩下2个盘子一直空着。

4. 盘子数量 ≤ 苹果数量（n ≤ m）
   拆成两大类，两类互斥，总数相加：

• 情况A：至少有一个盘子是空
  空掉一个盘子，问题简化为：m个苹果放到n-1个盘子：f(m, n-1)
• 情况B：所有盘子都至少有1个苹果，没有空盘子
  既然每个盘子至少1个，那我们可以每个盘子先拿走1个苹果，不改变分配方案种类。
  拿走n个苹果，剩下m-n个苹果继续放到n个盘子：f(m-n, n)

✅ 核心递推公式：
f(m,n)=f(m,n−1)+f(m−n,n) f(m,n) = f(m,n-1)+f(m-n,n)f(m,n)=f(m,n−1)+f(m−n,n)

手动模拟样例 m=7,n=3

f(7,3)=f(7,2)+f(4,3)f(7,3)=f(7,2)+f(4,3)f(7,3)=f(7,2)+f(4,3)

• f(7,2)：7苹果放2盘
• f(4,3)：4苹果放3盘，盘子>苹果 → f(4,4)
  层层递归，最后汇总得到8，和样例一致。

坑点重点（小白最容易踩）

1. 苹果、盘子都是相同！如果盘子不同（人不同），那是隔板法，完全不一样，不要搞混。
2. m=0的时候答案是1，不是0，很多新手在这里写错。
3. 递归终止条件顺序不能写反。

两种解法思路

解法1：纯递归代码，最简单，机考写的最快，适合本题数据范围很小（m,n<=10）
解法2：二维动态规划DP，递推填表，没有递归重复计算，适合数据更大的场景

三、解法1：递归版本 Python 代码 + 逐行详细注释

# HJ61 放苹果 递归解法# f(m, n): m个相同苹果放到n个相同盘子，允许空盘，返回分法总数defcount_way(apple,plate):# ========== 递归终止条件（出口） ==========# 情况1：苹果数量等于0，没有苹果可以放，只有1种方案：全部盘子空着ifapple==0:return1# 情况2：盘子只有1个，所有苹果只能放这盘子，只有1种方案ifplate==1:return1# ========== 盘子数量 > 苹果数量 ==========# 多余盘子一定是空的，多余盘子不影响分法，等价apple个苹果放到apple个盘子ifplate>apple:returncount_way(apple,apple)# ========== plate <= apple 核心递推公式 ==========# 方案A：至少1个盘子为空，等价apple苹果放到 plate-1个盘子case_empty=count_way(apple,plate-1)# 方案B：所有盘子都至少有1个苹果；每个盘子拿走1个苹果，剩下apple-plate个苹果放plate盘子case_no_empty=count_way(apple-plate,plate)# 总方案数 = 有空盘的方案 + 全部盘子都有苹果的方案total=case_empty+case_no_emptyreturntotal# 主程序入口if__name__=="__main__":# 读取一行输入，分割成两个字符串，转成整数 m苹果，n盘子m,n=map(int,input().split())# 调用函数计算方案总数res=count_way(m,n)# 打印结果print(res)

样例输入：7 3→ 输出8

四、解法2：二维动态规划DP版本，逐行注释

递归会重复计算子问题，DP预先填表，更适合大数。

# HJ61 放苹果 二维DP动态规划解法if__name__=="__main__":# 读取苹果m，盘子nm,n=map(int,input().split())# 创建二维dp数组 dp[i][j] 代表 i个苹果，j个盘子的分法数量# 数组范围：苹果0~m，盘子0~n，初始全部填充0dp=[[0]*(n+1)for_inrange(m+1)]# =========初始化边界条件=========# 条件1：苹果数量i=0，不管多少盘子，方案数=1forjinrange(n+1):dp[0][j]=1# 条件2：盘子数量j=1，不管多少苹果，方案数=1foriinrange(m+1):dp[i][1]=1# 双重循环填表，i苹果数量，j盘子数量，从小到大计算子问题foriinrange(1,m+1):forjinrange(2,n+1):# 盘子 > 苹果，多余盘子无效，dp[i][j] = dp[i][i]ifj>i:dp[i][j]=dp[i][i]else:# 递推公式：有空盘 + 全部盘子至少1个苹果dp[i][j]=dp[i][j-1]+dp[i-j][j]# 输出m个苹果n个盘子的结果print(dp[m][n])

两种方案对比

1. 递归：代码短，写起来快；小数据（m,n≤10）完全没问题；大数据会重复计算，效率低
2. DP：预先填表，没有重复计算，性能更好；代码行数略多

五、应用场景举例（相同物品无差别分配模型）

模型本质：整数拆分问题，把一个整数拆成最多n个非负整数之和，不考虑顺序

场景1：资源均分规划（物资发放）

救灾物资，物资完全相同，分发给n个社区，允许某些社区不领取物资；社区没有编号（不区分社区顺序），统计所有分配方案。

例：10箱矿泉水，分给4个社区，不计社区顺序，允许社区分不到，统计分配方案数量。

场景2：项目任务拆分

把m个完全一样的任务分配给n个小组，小组之间不区分，允许小组没有任务，求任务分配方案种类。

场景3：数学整数拆分（数论）

整数拆分经典模型：把数字m拆成最多n个非负整数相加，不计顺序，这就是本题数学原型。很多密码学、组合计数底层会用到整数拆分。

场景4：游戏道具分配

一堆完全相同的道具，放到n个储物背包，背包无编号，背包可以空，求分配方案。

场景5：预算切块

一笔总额固定资金，分成n份，不区分份的顺序，可以有0元份额，统计资金拆分方案。

⚠️重要区分：
如果盘子/人有编号（不同），就不是这道题，要用隔板法，方案数量会大很多，千万不要混淆。

六、费曼复盘总结

HJ61放苹果 =整数拆分，相同物品分到相同容器、允许空容器
核心思想：分两类（至少一个空盘 / 全部盘子都有苹果），两类相加。
递归出口：0苹果或者只有1盘子，方案数=1；盘子比苹果多，丢弃多余空盘子。

知识点清单：递归、分治、动态规划、组合数学整数拆分。

拓展练习（可选）

1. 变形题：盘子不能空，m个相同苹果n个相同盘子，求分法。
2. 变形题：盘子是不同的（人不一样），求方案（隔板法）。