牛客网 HJ61 放苹果题目链接https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf一、原题完整陈述题目描述把m个同样的苹果放在n个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法重点苹果相同、盘子相同。所以顺序无关。例如7个苹果3个盘子(5,1,1)和(1,5,1)视作同一种方案不能重复计数输入描述输入两个整数 m苹果数量、n盘子数量数据范围0≤m≤101≤n≤100 \le m \le 101 \le n \le 100≤m≤101≤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没有苹果 m0没有苹果所有盘子全空。只有1种方法啥都不放。f(0,n)1边界出口2只有1个盘子 n1所有苹果只能丢进这唯一盘子只有1种放法。f(m,1)1盘子数量 苹果数量nm盘子比苹果多必定有n-m个盘子是空的。空盘子不影响方案种类多余盘子直接忽略。等价于把m个苹果放到m个盘子。f(m,n)f(m,m)例3个苹果5个盘子等价3苹果放3盘子剩下2个盘子一直空着。盘子数量 ≤ 苹果数量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)手动模拟样例 m7,n3f(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和样例一致。坑点重点小白最容易踩苹果、盘子都是相同如果盘子不同人不同那是隔板法完全不一样不要搞混。m0的时候答案是1不是0很多新手在这里写错。递归终止条件顺序不能写反。两种解法思路解法1纯递归代码最简单机考写的最快适合本题数据范围很小m,n10解法2二维动态规划DP递推填表没有递归重复计算适合数据更大的场景三、解法1递归版本 Python 代码 逐行详细注释# HJ61 放苹果 递归解法# f(m, n): m个相同苹果放到n个相同盘子允许空盘返回分法总数defcount_way(apple,plate):# 递归终止条件出口 # 情况1苹果数量等于0没有苹果可以放只有1种方案全部盘子空着ifapple0:return1# 情况2盘子只有1个所有苹果只能放这盘子只有1种方案ifplate1:return1# 盘子数量 苹果数量 # 多余盘子一定是空的多余盘子不影响分法等价apple个苹果放到apple个盘子ifplateapple:returncount_way(apple,apple)# plate apple 核心递推公式 # 方案A至少1个盘子为空等价apple苹果放到 plate-1个盘子case_emptycount_way(apple,plate-1)# 方案B所有盘子都至少有1个苹果每个盘子拿走1个苹果剩下apple-plate个苹果放plate盘子case_no_emptycount_way(apple-plate,plate)# 总方案数 有空盘的方案 全部盘子都有苹果的方案totalcase_emptycase_no_emptyreturntotal# 主程序入口if__name____main__:# 读取一行输入分割成两个字符串转成整数 m苹果n盘子m,nmap(int,input().split())# 调用函数计算方案总数rescount_way(m,n)# 打印结果print(res)样例输入7 3→ 输出8四、解法2二维动态规划DP版本逐行注释递归会重复计算子问题DP预先填表更适合大数。# HJ61 放苹果 二维DP动态规划解法if__name____main__:# 读取苹果m盘子nm,nmap(int,input().split())# 创建二维dp数组 dp[i][j] 代表 i个苹果j个盘子的分法数量# 数组范围苹果0~m盘子0~n初始全部填充0dp[[0]*(n1)for_inrange(m1)]# 初始化边界条件# 条件1苹果数量i0不管多少盘子方案数1forjinrange(n1):dp[0][j]1# 条件2盘子数量j1不管多少苹果方案数1foriinrange(m1):dp[i][1]1# 双重循环填表i苹果数量j盘子数量从小到大计算子问题foriinrange(1,m1):forjinrange(2,n1):# 盘子 苹果多余盘子无效dp[i][j] dp[i][i]ifji: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])两种方案对比递归代码短写起来快小数据m,n≤10完全没问题大数据会重复计算效率低DP预先填表没有重复计算性能更好代码行数略多五、应用场景举例相同物品无差别分配模型模型本质整数拆分问题把一个整数拆成最多n个非负整数之和不考虑顺序场景1资源均分规划物资发放救灾物资物资完全相同分发给n个社区允许某些社区不领取物资社区没有编号不区分社区顺序统计所有分配方案。例10箱矿泉水分给4个社区不计社区顺序允许社区分不到统计分配方案数量。场景2项目任务拆分把m个完全一样的任务分配给n个小组小组之间不区分允许小组没有任务求任务分配方案种类。场景3数学整数拆分数论整数拆分经典模型把数字m拆成最多n个非负整数相加不计顺序这就是本题数学原型。很多密码学、组合计数底层会用到整数拆分。场景4游戏道具分配一堆完全相同的道具放到n个储物背包背包无编号背包可以空求分配方案。场景5预算切块一笔总额固定资金分成n份不区分份的顺序可以有0元份额统计资金拆分方案。⚠️重要区分如果盘子/人有编号不同就不是这道题要用隔板法方案数量会大很多千万不要混淆。六、费曼复盘总结HJ61放苹果 整数拆分相同物品分到相同容器、允许空容器核心思想分两类至少一个空盘 / 全部盘子都有苹果两类相加。递归出口0苹果或者只有1盘子方案数1盘子比苹果多丢弃多余空盘子。知识点清单递归、分治、动态规划、组合数学整数拆分。拓展练习可选变形题盘子不能空m个相同苹果n个相同盘子求分法。变形题盘子是不同的人不一样求方案隔板法。