首页 > 试题广场 >

放苹果

[编程题]放苹果
  • 热度指数：12131 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入描述:
每行均包含二个整数M和N，以空格分开。1<=M，N<=10。


输出描述:
对输入的每组数据M和N，用一行输出相应的K。
示例1

输入

7 3

输出

8
算法知识视频讲解
开通博客
头像 czhappy
发表于 2020-04-06 16:00:32
思路 设f(m, n)表示将m个苹果放到n个盘子中的方法数 把问题分成两种情况 盘子数n > 苹果数m ：则无论怎样放必然有n - m个空盘子，这些盘子都废掉了。实际上f(m , n) = f(m , m) 盘子数n <= 苹果数m: 这时候考虑到底是每个盘子都放苹果还是留至少一个 展开全文
去ta的博客 赞 (32) 回复(3) 收起
头像 csyfZhang
发表于 2020-04-21 11:43:40
https://blog.csdn.net/csyifanZhang/article/details/105652758↑为了更好的阅读体验 这道题是一个模板题，所以先上原模板：这样的划分被称作的划分数，特别地，时称作 的划分数、DP不仅对于求解最优问题有效,对于各种排列组合的个数、概率或者期望之类 展开全文
去ta的博客 赞 (22) 回复(0) 收起
头像 位琬续
发表于 2021-03-18 11:14:43
思路：第一次尝试（错误）：将M个苹果转换成为不同重量堆的苹果，使用0-1背包解决，失败：原因是在苹果分堆在聚合过程后无法控制总数恰好等于M； 第二次尝试（错误）：注意到M个苹果放到N个盘子里，依次相加空出0个、1个……N个盘子各个数量，失败；原因是调用M个苹果装到N-k个盘子会有重复：例如将（M=4 展开全文
去ta的博客 赞 (13) 回复(0) 收起
头像 Huster水仙
发表于 2023-02-12 23:19:38
DP：M个物品划分成N份 关键：比较盘子和苹果的个数大小 dp[i][j]：i个苹果分给j个盘子 ①盘子比苹果多：一定有盘子是空的，摔掉多余空盘子即可： dp[i][j]=dp[i][i] ②盘子不比苹果多: 要么每个盘子都非空，相当于先给每个盘子放一个苹果，只用考虑剩下的i-j个苹果：dp[i- 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 宁静的冬日
发表于 2022-03-06 13:07:49
【C++】本题可以直接用递归，深度浅，不需要动态规划 ">#include<string> #include<algorithm> using namespace std; #define MAX 100 //求m个苹果放n个盘子中的方法数 int ways(int m, i 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 小帅哥HLB
发表于 2022-03-10 10:58:33
#include <cstdio> #include <string> #include <algorithm> using namespace std; //求m个苹果放n个盘子中的方法数 int ways(int m, int n) { //边界条件 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 在考古的小鱼干很有气魄
发表于 2023-03-08 22:27:10
#include <bits/stdc++.h> #define MAX 10 using namespace std; int fun(int m, int n) { if (m == 0 || n == 1) //没有苹果或只有一个盘子时，都是一种放法 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客440904392号
发表于 2024-09-29 13:11:02
import java.util.Arrays; import java.util.Scanner; public class Main { private static int[][] dp; public static void main(String[] args) { 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客822427309号
发表于 2023-03-16 21:46:24
#include<iostream> using namespace std; int f(int m, int n) { //使用递归的方式 当只有一个盘子 或者没有苹果的时候函数返回一种结果（一个苹果的时候，即返回f（1，1）为1） if ((m == 0) || (n 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛可乐111b
发表于 2024-03-14 15:46:51
#include <iostream> #include<queue> #include<algorithm> using namespace std; struct state{ int left; int plates[20]; }; bo 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
55条回答 10133浏览

热门推荐

通过挑战的用户

查看代码

相关试题

放苹果

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号