把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：5、1、1 和 1、5、1 是同一种分法，即顺序无关。
[编程题]放苹果
/*
我的QQ：825580813（欢迎来一起讨论，刷题，PK）。
首先用递归的思想来思考这道题：
1，递归出口：当只有一个盘子或者 含有 0 个 或 1 个苹果的时候只有一种方法
2，当盘子数 n 大于苹果数 m 时，则必有 n - m 个空盘子，所以只需求 m 个盘子
放 m 个苹果时的方法数即可，
3，当盘子数 n 小于等于 苹果数 m 时，总方法数 = 当含有一个空盘子时的方法数
+ 不含空盘子时的方法数。
原因：当在求只含有一个空盘子时的方法数时，已经包含了含有 2 ~ n - 1 个空盘子 的情况。
不含空盘子的计算：先将每个盘子装一个苹果，则问题变成了求 n 个盘子放 m - n
个苹果的方法数了。
其间，还可用记忆搜索优化（此处不再详讲）
然后用动态规划来优化代码：
新建一个动态规划表 dp；dp[i][j] 表示 i 个盘子放 j 个苹果的方法数。
则 当 i > j 时，dp[i][j] = dp[i - (i - j)][j] = dp[j][j](原因上面已经讲过）
当 i <= j 时，dp[i][j] = dp[i - 1][j] + dp[i][j - i];
最后dp[n][m] 就是所求。
最后，可用空间压缩的办法进一步优化代码：
由于dp[i][j] 依赖其左边的 dp 与其的距离不太确定，所以就按行分割dp表啦*_*.
（其实也还是有一定规律的，就是当 i < j 时左边依赖的 dp 与其的距离为 i ，
只需用一个更小的数组来记录其左边与其相距为 i 的几个值即可，
这里代码实现就不写了，望君可写出）。
如果听了左神的课，这里的解释就很容易懂了，由于本人能力有限，只能讲到这里了。
*/
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
int process (int m, int n)
{
if( m == 0 || m == 1 || n == 1 )
{
return 1;
}
if( n > m )
{
return process (m, m);
}
else
{
return process (m, n - 1) + process (m - n, n);
}
}
int putApple1 (int m, int n)
{
return process (m, n);
}
int** getdp1 (int m, int n)
{
if( m == 0 || m == 1 || n == 1 )
{
return NULL;
}
int **dp = new int *[n + 1];
for( int i = 0; i <= n; i++ )
{
dp[i] = new int[m + 1];
for( int j = 0; j <= m; j++ )
{
dp[i][j] = 1;
}
}
for( int i = 2; i <= n; ++i)
{
for( int j = 2; j <= m; ++j)
{
if( i > j )
{
dp[i][j] = dp[j][j];
}
else
{
dp[i][j] = dp[i - 1][j] + dp[i][j - i];
}
}
}
return dp;
}
int putApple2 (int m, int n)
{
if( m == 0 || m == 1 || n == 1 )
{
return 1;
}
int **dp = getdp1 (m, n);
return dp[n][m];
}
int* getdp2 (int m, int n)
{
if( m == 0 || m == 1 || n == 1 )
{
return NULL;
}
int *dp = new int[m + 1];
for( int i = 0; i <= m; i++ )
{
dp[i] = 1;
}
for( int i = 2; i <= n; ++i)
{
for( int j = 2; j <= m; ++j)
{
if( i <= j )
{
dp[j] = dp[j] + dp[j - i];
}
}
}
return dp;
}
int putApple3 (int m, int n)
{
if( m == 0 || m == 1 || n == 1 )
{
return 1;
}
int *dp = getdp2 (m, n);
return dp[m];
}
int main ()
{
srand ((unsigned)time (NULL));
for( int i = 0; i < 1000; i++ )
{
int m = rand () % 20 + 1;
int n = rand () % 20 + 1;
cout << "case : " << i << endl;
cout << "苹果数 : " << m << "\t盘子数：" << n << endl;
int a1 = putApple1 (m, n);
int a2 = putApple2 (m, n);
int a3 = putApple3 (m, n);
if( a1 != a2 )
{
cout << "\n\n\t~~!!!Error!!!~~\n\n";
cout << "a1 = " << a1 << "\ta2 = " << a2 << "\ta3 = " << a3 << endl;
break;
}
cout << "a1 = " << a1 << "\ta2 = " << a2 << "\ta3 = " << a3 << endl;
cout << endl;
}
cout << "\n\nEND\n\n";
return 0;
}
编辑于 2017-06-05 22:04:02
回复(4)
整数划分的一种：求将一个整数m至多划分成n个数有多少种情况 变形：求将一个整数m划分成n个数有多少种情况 dp[m][n] = dp[m-n][n] + dp[m-1][n-1]; 对于变形后的问题，存在两种情况： 1. n 份中不包含 1 的分法，为保证每份都 >= 2，可以先拿出 n 个 1 分到每一份，然后再把剩下的 m- n 分成 n 份即可，分法有: dp[m-n][n] 2. n 份中至少有一份为 1 的分法，可以先那出一个 1 作为单独的1份，剩下的 m- 1 再分成 n- 1 份即可，分法有：dp[m-1][n-1] import java.util.Scanner; public class Main { public static final int maxn = 25; public static void main(String[] args) { int[][] dp = new int[maxn][maxn]; for(int i=1;i<maxn;i++){ dp[i][1] = 1; dp[i][i] = 1; } for(int i=1;i<maxn;i++){ for(int j=2;j<maxn;j++){ if(i>j) dp[i][j] = dp[i-j][j] + dp[i-1][j-1]; else if(i == j) dp[i][j] = 1; else dp[i][j] = 0; } } Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int m = sc.nextInt(); int n = sc.nextInt(); int res = 0; for(int i=1;i<=n;i++) res += dp[m][i]; System.out.println(res); } } }
编辑于 2016-02-21 17:50:25
回复(0)
动态规划
苹果 < 盘子 = 去掉一个盘子的分法
苹果 = 盘子 = 有空盘子,去掉空盘子的分法 + 1(每个盘子一个的分法)
苹果 > 盘子，有两种情况 1、每个盘子都有苹果，= 每个盘子都拿掉一个苹果后的分法 2、有空盘子(至少一个)，= 去掉空盘子后的分法 相加
#include<iostream>
using namespace std;
int main()
{
int m, n;
while (cin>>m>>n)
{
int** dp = new int* [m + 1];//dp[i][j]表示i个苹果放在j个盘子中时，有多少种分法
for (int i = 1; i <= m; i++)
{
dp[i] = new int[n + 1];
//base case只有一个盘子时或只有一个水果时，只有一种分法
dp[i][1] = 1;
for (int j = 1; j <= n; j++)
dp[1][j] = 1;
}
for (int i = 1; i <= m; i++)
{
for (int j = 2; j <= n; j++)
{
if (i < j) //苹果比盘子少时，等于去掉一个盘子的分法
dp[i][j] = dp[i][j - 1];
//苹果和盘子一样多时，等于有空盘子去掉空盘子的分法+每个盘子一个的分法
else if (i == j)
dp[i][j] = dp[i][j - 1] + 1;
/*苹果比盘子多时，有两种情况
1、每个盘子都有苹果，那就等于每个盘子都拿掉一个苹果后的分法数
2、有空盘子(至少一个)，就等于去掉空盘子后的分法*/
else
dp[i][j] = dp[i - j][j] + dp[i][j - 1];
}
}
cout << dp[m][n] << endl;
for (int i = 1; i <= m; i++)
delete[] dp[i];
delete[] dp;
}
return 0;
}
发表于 2020-07-11 16:07:52
回复(0)
//让每个盘子里的苹果数不减，保证解唯一
#include<cstdio>
#include<cstring>#include<algorithm>
using namespace std;
int dp[22][22][22];
int dfs(int x,int y,int pre)//x个苹果,y个盘子,前一个盘子里有pre个苹果
{
if(x<pre) return dp[x][y][pre]=0;
if(x==0) return dp[x][y][pre]=0;
if(y==1) return dp[x][y][pre]=1;
if(dp[x][y][pre]!=-1) return dp[x][y][pre];
int ret=0;
for(int i=pre;i<=x;i++)
ret+=dfs(x-i,y-1,i);
return dp[x][y][pre]=ret;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,-1,sizeof(dp));
printf("%d\n",dfs(n,m,0));
}
return 0;
}
发表于 2018-05-07 01:34:10
回复(0)
问题“将M个苹果放入N个盘子，有几种放法”可以扩展为“将M个苹果放入N个盘子，每个盘子最少放K个，有几种放法”，即：
对于i（K<=i<=M）,j（1<=j<=N），若前j个盘子全部放i个苹果，那么问题可变为子问题：剩下M-i*j个苹果放入N-j个盘子，每个盘子最少放i+1个，有几种放法。
PS.本题允许空盘子存在，第一次做出错，才发现问题出在这儿，即K的初值取0而不是1
Python代码如下：
while True:#允许读入多组样例
try:
def solution(m,n,k):#m个苹果放入n个盘子，每个盘子不得少于k
#若n个盘子每个盘子放入k个恰好放完，则有1种解法
if k*n==m:
return 1
#若剩下的m个苹果无法使得每个盘子的苹果都不少于k个，则无解
elif k*n>m:
return 0
res=0
for i in range(k,m+1):
for j in range(1,n+1):
#若前j个盘子每个盘子都放入i个苹果，那么问题变为剩下m-i*j个苹果放入剩下n-j个盘子，每个盘子至少放i+1个，有几种放法
res+=solution(m-i*j,n-j,i+1)
return res
#读入数据
m,n=list(map(int,input().split(' ')))
#输出结果
print(solution(m,n,0))
except EOFError:
break
编辑于 2018-02-13 19:17:19
回复(0)
#include<stdio.h>
#include<string.h>
int dp[105][105][105];
int main(){
int N,M,i,j,T,k;
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&M,&N)!=EOF){
memset(dp,0,sizeof(dp));
for(k=1;k<=N;k++)
for(i=0;i<=M;i++)
for(j=0;j<=i;j++)
dp[k][i][j]=1;
for(k=2;k<=N;k++)
for(i=1;i<=M;i++)
for(j=1;j<=M;j++){
dp[k][i][j]=dp[k][i-1][j];
if(j>=i) dp[k][i][j]+=dp[k-1][i][j-i];
}
printf("%d\n",dp[N][M][M]);
}
}//把问题转化为:在 0...M 中 , 只取 N 个数 , 使得他们的和为M的情况有多少种
// 那么 dp[k][i][j]的意义就是 在0到i中 取k个数 使得和为j的情况数
发表于 2017-08-05 18:35:36
回复(0)
两种方案
import java.util.Scanner;
// write your code here
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int m = in.nextInt();
int n = in.nextInt();
int count = setApple(m, n);
System.out.println(count);
}
}
// m是苹果个数，n为盘子个数
public static int setApple(int m, int n) {
// if (m <= 0 || n == 1)
// return 1;
// if(m < n)
// return setApple(m, m); // 苹果数目小于盘子
// else
// return setApple(m, n - 1) + setApple(m - n, n); // 两种情况：留一个空盘子不放+放n-1个盘子，剩下一个放m-n
// dp[i][j]表示i个苹果，j个盘子的摆放策略
int maxn = 25;
int[][] dp = new int[maxn][maxn];
for (int i = 0; i < maxn; i++){
dp[i][0] = 1;
dp[i][1] = 1;
}
for (int j = 0; j < maxn; j++){
dp[0][j] = 1;
dp[1][j] = 1;
}
for(int i = 2; i < maxn; i++){
for(int j = 2; j < maxn; j++){
if(i >= j)
dp[i][j] = dp[i][j - 1] + dp[i - j][j];
else
dp[i][j] = dp[i][i]; // 当苹果数目小于盘子时
}
}
return dp[m][n];
}
}
发表于 2017-07-30 21:35:19
回复(0)
整数划分问题
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
using namespace std;
int main(int argc, char** argv)
{
//freopen("in.txt", "r", stdin);
int n,m;
while (cin >> m >> n)
{
vector<vector<int>> dp(n + 1, vector<int>(m + 1,0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (j >= i) dp[i][j] = dp[i - 1][j] + dp[i][j - i];
else dp[i][j] = dp[i - 1][j];
}
}
cout << dp[n][m] << endl;
}
return 0;
}
发表于 2017-07-11 18:43:02
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int m = sc.nextInt();
int n = sc.nextInt();
System.out.println(fun(m, n));
}
}
public static int fun(int m, int n) {
if(m == 0 || n == 1) return 1;
if(n > m) return fun(m, m);
else return fun(m, n - 1) + fun(m - n, n);
}
}
发表于 2016-10-15 16:50:18
回复(0)
放法：
每一个子过程中
1.每个盘子上都要放一个。
2.至少有一个盘子不放。 (而至少有n个不放是每次有一个不放递推得来)。
3.每个放置过程由1，2两步构成。
当只有一个盘子 或 只有一个果子，只有一种方法。
编辑于 2015-11-04 23:19:23
回复(0)
#include <iostream>usingnamespacestd;intdp(intm,intn){// 递归出口：有0个苹果 || 只有1个盘子if(m == 0 || n == 1)return1;if(n>m)// 盘子比较多，肯定有空盘子，去掉必空的盘子returndp(m, m);else// 苹果比较多：// 1：至少有一个空盘子，拿掉这个空盘子// 2：每个盘子都有苹果，各拿掉一个苹果（极限是最少的有1个苹果）returndp(m, n - 1) + dp(m - n, n);}intmain(){intm, n;while(cin >> m >> n)cout << dp(m, n) << endl;return0;}
编辑于 2017-10-31 16:43:13
回复(0)
这个方法太厉害了，让我们来分析一下
构造出口条件：
1、只有1个盘子，就只有1种方法了
2、有0个苹果，也就只有1种方法了
#include <iostream>
using namespace std;
int dp(int m, int n)
{
// 递归出口：有0个苹果 || 只有1个盘子
if (m == 0 || n == 1)
return 1;
if (n>m) // 盘子比较多，肯定有空盘子，去掉必空的盘子
return dp(m, m);
else // 苹果比较多：
// 1：至少有一个空盘子，拿掉这个空盘子
// 2：每个盘子都有苹果，各拿掉一个苹果（极限是最少的有1个苹果）
return dp(m, n - 1) + dp(m - n, n);
}
int main()
{
int m, n;
while (cin >> m >> n)
cout << dp(m, n) << endl;
return 0;
}
发表于 2016-09-01 16:43:29
回复(13)
参考了各位撸友的解析,我补充一点对自认为的难点的理解:
# 难点: 当苹果大于盘子时,(这是大前提,注意哦) 我们怎么确定有多少种放法. 此时我们考虑了分类.
# 思路来源: 分类计数原理:完成一件事情有n类办法,那么完成这件事共有N=m1+m2+…+m
n
种不同的方法.
# 分类:
分为有空盘和没有空盘的两种情况.
# 检查分类
1. 完备性
是否囊括所有情况, 所有的放苹果方法,要么有空盘,要么没有空盘.
2. 分类是否重复
一类有空盘,一类无空盘,不会重复.
# 分类后,我们如何操作可以保证满足分类条件
1. 保证有空盘
单独拿一个盘子不放,此时的情形,对于放法数而言,是不是相当于f(apple, plate-1).
2. 保证没有空盘
首先每个盘子放一个苹果,这样不就可以保证了,此时的情形,对于放法数而言,是不是相当于f(apple-plate,plate)
以上
编辑于 2017-03-31 16:51:44
回复(2)
动态规划算法
#include <iostream>
using namespace std;
int main()
{
int m, n, i, j, dp[21][21];
while(cin >> m >> n)
{
for (i = 1; i <= m; i++) dp[i][1] = 1;
for (i = 1; i <= m; i++)
{
for (j = 2; j <= n; j++)
{
if (i < j) dp[i][j] = dp[i][j - 1];
else if(i == j) dp[i][j] = dp[i][j - 1] + 1;
else dp[i][j] = dp[i - j][j] + dp[i][j - 1];
}
}
cout << dp[m][n] << endl;
}
return 0;
}
发表于 2018-05-08 23:17:11
回复(1)
动态规范
while True:
try:
m,n = list(map(int,input().split()))
reuslts = [[0 for i in range(n + 1)] for j in range(m + 1)] #reuslts[i][j]表示j个盘子装i个苹果
for i in range(1,m+1):
reuslts[i][1] = 1
for j in range(2,n+1):
if i < j: #盘子比苹果多并不会增加分法
reuslts[i][j] = reuslts[i][j - 1]
elif i == j: #盘子和苹果一样多，相当于多了一个全部盘子只摆一个，其他摆法起码有一个空盘
reuslts[i][j] = reuslts[i][j - 1] + 1
else: #盒子比苹果少，等于有一个空盘加上全部盘摆上一个苹果剩余的摆法
reuslts[i][j] = reuslts[i - j][j] + reuslts[i][j - 1]
print(reuslts[m][n])
except Exception as message:
print(message)
break
编辑于 2018-10-03 01:12:58
回复(0)
参考递归的方法，改写成传统dp形式。
首先两个循环吧m = 0和n = 1的元素都置位1。然后在一个双重循环逐一计算dp[i][j]的值。
- 若i < j，dp[i][j] = dp[i][i]，苹果比盘子少，肯定有空盘子，空盘子不影响，可以直接去掉。
- 若i >= i，dp[i][j] = dp[i][j - 1] + dp[i - j][j]，苹果比盘子多，即至少有一个盘子空着的情况（dp[i][j - 1] ）加上所有盘子都不空（每个盘子去掉一个苹果，即去掉j个苹果，dp[i - j][j]）的情况。
最后输出dp[m][n]即可。
#include <iostream>
using namespace std;
int dp[21][21];
int main(void) {
int m, n;
while (cin >> m >> n) {
for (int i = 0; i <= n; ++i) {
dp[0][i] = 1;
}
for (int i = 0; i <= m; ++i) {
dp[i][1] = 1;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (i < j) {
dp[i][j] = dp[i][i];
}
else {
dp[i][j] = dp[i][j - 1] + dp[i - j][j];
}
}
}
cout << dp[m][n] << endl;
}
return 0;
}
编辑于 2018-04-09 16:03:44
回复(1)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int m,n;
while(cin>>m>>n){
vector<int>dp(m+1,0);
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=m;j++){
dp[j]+=dp[j-i];
}
}
cout<<dp[m]<<endl;
}
}
发表于 2025-03-23 15:06:38
回复(0)
动态规划求解，注意盘子可能为空
#include <stdio.h>
#include <string.h>
#define MAX 20
long long int dp[MAX][MAX];
int main() {
int n,m;
while (scanf("%d %d",&m,&n)!=EOF) {
//苹果如果是0，盘子如果1个分法都是1种，问题的边界
memset(dp, 0,sizeof(dp));
for(int i=0;i<=m;i++){
dp[i][1]=1;
}
for(int i=1;i<=n;i++){
dp[0][i]=1;
dp[1][i]=1;
}
for(int i=2;i<=m;i++){ //i是苹果数，j是盘子数
for(int j=2;j<=n;j++){
if(i>=j){
dp[i][j]=dp[i][j-1]+dp[i-j][j];
}else{
dp[i][j]=dp[i][i]; //盘子大于苹果
}
}
}
printf("%lld\n",dp[m][n]);
}
}
发表于 2025-03-23 10:53:28
回复(0)
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
int dp[21][21] = {0};
// dp[m][n] m个苹果放入n个盘子
int m, n;
while (scanf("%d %d", &m, &n) != EOF)
{
memset(dp, 0, 21 * 21);
for (int i = 0; i <= m; i++)
{
dp[i][1] = 1;
}
for (int i = 1; i <= n; i++)
{
dp[1][i] = 1;
dp[0][i] = 1;
}
for (int i = 2; i <= m; i++)
{
for (int j = 2; j <= n; j++)
{
// 苹果比盘子多
if (i >= j)
{
dp[i][j] = dp[i][j - 1] + dp[i - j][j];
}
else
{
dp[i][j] = dp[i][i];
}
}
}
printf("%d\n", dp[m][n]);
}
return 0;
}
发表于 2025-02-13 23:26:09
回复(0)
用了回溯的思想
#include <iostream> #include<vector> using namespace std;提交观点 //回溯：得到和为sum的两个数的组合。子元素是0~n vector<int> path; int all_choices = 0; void backt(int panzi, int n, int star, int sum) { //元素可以重复用。的组合 if (sum == n && path.size() == panzi) { all_choices++; } else if (sum < n) { for (int i = star; i <= n; i++) { sum += i; path.push_back(i); backt(panzi, n, i, sum); sum -= i; path.pop_back(); } } } int main() { //组合问题。遍历数组 //当空盘子数量=0~N-1。分别求有几种方法 //当苹果多过盘子。空盘子=0~p-1,堆数=1~p。当盘子p多过苹果a。空盘子=p-a~p-1,堆数=1~a int dui = 0, p, a; while (cin >> a >> p) { all_choices=0; if (p > a) dui = a; else dui = p; for (int i = 1; i <= dui; i++) { backt(i, a, 1, 0); } cout << all_choices<<endl; } } // 64 位输出请用 printf("%lld")
编辑于 2024-03-21 19:11:26
回复(0)
问题信息
难度：
57条回答
201收藏
17869浏览
通过挑战的用户
查看代码-
2023-03-11 12:36:44
-
2023-01-06 09:49:42 -
2022-11-04 11:59:15
-
2022-09-09 01:16:00 -
2022-09-08 21:18:25
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
