首页 > 试题广场 >

放苹果

[编程题]放苹果

热度指数：161923 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 我们需要将 $m$ 个相同的苹果放入 $n$ 个相同的盘子中，允许有的盘子空着不放。求解有多少种不同的分法。

输入描述:

输入两个整数  代表苹果数、盘子数。

输出描述:

输出一个整数，代表不同的分法数量。

示例1

输入

3 2

输出

说明

在这个样例中，有 、 这两种不同的分法。

示例2

输入

7 3

输出

说明

注意，由于苹果和盘子都是相同的，所以  和  是同一种分法。

算法知识视频讲解

查看答案及解析

Java

牛客160935469号

思路有点抽象……

import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int apples = in.nextInt();
        int contains = in.nextInt();
        System.out.println(getMethods(apples, contains));
    }

    public static int getMethods(int apples, int contains) {
        // 苹果数量刚好每盘子一个或者只剩最后一个盘子，计一种方法
        if (apples == 0 || contains == 1) {
            return 1;
        } 
        if (apples < 0) { // 苹果数量不够每盘子一个
            return 0;
        }
        // 每个盘子至少放了一个的情况和有若干个盘子没放的情况
        return getMethods(apples-contains, contains) + getMethods(apples, contains-1);
    }
}

发表于 2024-10-01 16:16:01 回复(0)

Java

牛客700990974号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int m = in.nextInt();

int n = in.nextInt();

System.out.println(split(m, n));

}

private static int split(int m, int n) {

// // 苹果0个或者1个，放哪个盘子都一样，1种；盘子只有1个，只能全部放入当前盘子，1种

// if (m <= 1 || n == 1)

// return 1;

// // 盘子多，相当于m个苹果放到m个盘子

// if (n > m) {

// return split(m , m);

// }

// // 盘子少或者盘子与苹果一样多：要么空1个盘子，接下来递归；要么每个盘子放一个，进行递归

// return split(m, n -1) + split(m - n, n);

// 转dp

int[][] dpArray = new int[m + 1][n + 1];

for (int col = 0; col < dpArray[0].length; col++) {

dpArray[0][col] = 1;

dpArray[1][col] = 1;

}

for (int row = 0; row < dpArray.length; row++) {

dpArray[row][1] = 1;

}

for (int row = 2; row < dpArray.length; row++) {

for (int col = 2; col < dpArray[0].length; col++) {

dpArray[row][col] = row < col ? dpArray[row][row] : dpArray[row][col -1] + dpArray[row -col][col];

}

return dpArray[m][n];

}

编辑于 2023-12-11 19:54:02 回复(0)

Java

vhsl

package com.huawei.item.easy;

import java.util.Scanner;

public class SixtyOne {
    public static void main(String[] args) {
        //把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
        //注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(); // m个苹果
        int n = in.nextInt(); // n个盘子
        int[][] dp = new int[m][n];
        int sum = uniquePaths(m, n);
        System.out.println(sum);
    }

    private static int uniquePaths(int m, int n) {
        // dp[m][n] = dp[m][n-1]+dp[m-n][n]
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for (int i = 0; i < m + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                // 初始化数据
                if (i <= 1 || j <= 1) {
                    dp[i][j] = 1;
                    continue;
                }
                // 动态规划
                if (i < j) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }
        return dp[m][n];
    }


}

第一次做动态规划，研究一上午，还是看了其他博主讲的动态规划的内容，看完会有些感受。

继续往下推导。

最后如果剩下1个苹果或者0个苹果，不管有多少盘子，无论是1个苹果1个盘子，还是1个苹果10个盘子，都只有一种放法

或者只剩下1个盘子，无论剩多少苹果，也都只有一种放法。

所以当 m <= 1 || n <= 1 时，初始化数值为1.

            if (i <= 1 || j <= 1) {
                dp[i][j] = 1;
                continue;
            }

放苹果有两种情况：

所有盘子都放苹果 2. 有1个或多个盘子放苹果

当苹果数量<盘子数量时，不可能所有盘子都放苹果，只能去除一个盘子，向下计算。

例如：2个苹果5个盘子的放置方法 = 2个苹果4个盘子的放置方法

if (i < j) {    dp[i][j] = dp[i][j - 1];}

当苹果数量>=盘子数量时，上述两种情况都可以

例如：7个苹果放3个盘子 = 7个苹果放2个盘子 + 4个苹果放3个盘子里

else {    dp[i][j] = dp[i][j - 1] + dp[i - j][j];}

发表于 2023-07-09 13:18:17 回复(0)

Java

SUMMERENT

//递归法
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int a = in.nextInt();
        int b = in.nextInt();
        int count = count(a, b);
        System.out.println(count);

    }
    public static int count(int a, int b) {
        if(a ==0 || b ==1){
            return 1;
        }else if(a < b){
            return count(a,a);
        }else {
            return count(a,b-1)+count(a-b,b);
        }
    }
}

发表于 2023-06-01 16:53:30 回复(0)

Java

牛客488949482号

import java.util.Scanner;

//状态：分苹果的种类count

//选择：盘子中所有摆放的可能

//函数的定义：f(m,n) = f(m,n-1)+f(m-n,n);

//base case:苹果为0或1时，只有一种方法；

// 盘子为1时，只有一种方法；

public class Main {

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

while(sc.hasNext()){

int apple = sc.nextInt();

int n = sc.nextInt();

int[][] dp = new int[apple+1][n+1];

for(int i = 0;i <= n;i++){//base case

dp[0][i] = 1;//苹果为0时

dp[1][i] = 1;//苹果为1时

}

for(int i =0;i <=apple;i++) {//盘子为1时

dp[i][1] = 1;

dp[i][0] = 0;//盘子为0

}

for(int i = 2;i <= apple;i++){//种数=其中一个盘子不放+每个盘子放1个

for(int j = 2;j <= n;j++){

if(i-j<0){

dp[i][j]= dp[i][j-1];

}else{

dp[i][j] = dp[i][j-1]+dp[i-j][j];

}

System.out.println(dp[apple][n]);

}

发表于 2023-04-19 20:43:25 回复(0)

Java

牛明月

为了保证类似1 1 5 和 5 1 1 和 1 5 1这类划分重复，直接限定从开始放置某个盘子起，每个盘子放置的数量具有单调性，我这里采用单调不增；

import java.util.*;
//由于本体苹果是相同的，盘子也是相同的
//所以每个盘子中的苹果只区分个数，每一个放的盘子也不能分先后；
//所以我们在操作某一个盘子时只取i个苹果，但我们要保证我们分苹果的数量单调不减或者单调不增
//此处采用单调不增，即下一个盘子放的苹果数量<=当前放的苹果数量
//当前放的苹果数量不能低于剩余苹果数量平均放到剩余盘子中的数量，即(m-i)<=i*(n-1)
//递归计算，除了携带m、n之外，还需传递当前可取最大苹果数max
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();
            System.out.println(getAnswer(m, n,m));
        }
    }
    public static int getAnswer(int m,int n,int max){//max用来限制当前盘子最大能取多少个苹果
        if(n==1||m==0) {//定义只有一个盘子 或者只有0个苹果的分法
            return 1;
        }
        int answersCount = 0;
        for (int i = 1; i <= Math.min(m,max); i++) {
            if((m-i)<=i*(n-1)){
                answersCount+=getAnswer(m-i,n-1,i);
            }
        }
        return answersCount;
    }
}

发表于 2023-03-21 19:30:46 回复(0)

Java

FTL1ght

重点在于分类，以及结束条件的理解

import java.util.Scanner;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(System.in);
        
        while (in.hasNextInt()) { 
            int apple = in.nextInt();
            int plate = in.nextInt();
            int res = divide(apple,plate);
            System.out.println(res);
        }
    }

    //总共两大种情况
    //1. apple数量大于plate数量，可以分为空盘子或不空盘子（即每个盘子至少放一个）
    //2. apple数量小于plate数量，此时，至少有plate-apple个空盘（对于计算放盘的数量而言，空盘无效），只当做apple = plate来计算(这样会把计算交给第一类)
    //结束条件：apple == 0(第一大类的不空盘子可能的结果（苹果数量<=盘子数量时的一种可能性）);plate == 1(第一大类的不空盘子可能的结果/第一大类的空盘子可能的结果)
    public static int divide(int apple,int plate){
        if(apple == 0 || plate == 1){
            return 1;
        }else if(apple<plate){
            return divide(apple,apple);
        }else{
            return divide(apple-plate,plate) + divide(apple,plate - 1);
        }
    }
}

发表于 2023-02-12 15:01:33 回复(0)

Java

树荫下的天空

我感觉

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
//        苹果数
        int m = in.nextInt();
//        果盘数
        int n = in.nextInt();
        System.out.println(dfs(m, n));

    }

    /**
     * @param m 苹果
     * @param n 盘子
     * @return
     */
    private static int dfs(int m, int n) {
        if (m == 0 || n == 1) {
            return 1;
        }
        if (n > m) {
//            盘子比苹果多，肯定会空出盘子
            return dfs(m, m);
        }
        return
//                    每个盘子都有苹果,相当于求解 m - n个苹果 放在盘子里（每个盘子都有一个苹果）有几种方法
            dfs(m - n, n)
            +
//                    有空盘子
            dfs(m, n - 1);

    }
}

挺难的

发表于 2022-11-14 10:37:48 回复(0)

Java

Sawyer_lILi

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int m = sc.nextInt();

int n = sc.nextInt();

System.out.println(divide(m,n));

}

public static int divide(int m,int n) {

if(m==0||n==1){

return 1;

}

//盘子比苹果多的时候，最多用到m个盘子

//而盘子没有区别，也是就是说这种情况同于

//m个苹果m个盘子

if (n>m){

return divide(m,m);

}

//苹果数>=盘子数时，可以先简化为一个盘子不放苹果时的方法f(m,n-1)

//加上每个盘子都先防上一个苹果后，剩下m-n个苹果放n个盘子的放法

//这两种设想情况一定不会有重复的部分，也不会再递归过程中少算一种情况

//递归调用，直到m=0或者n=1的终结条件

else {

return divide(m,n-1)+divide(m-n,n);

}

这题看语文水平，好多题解说不出自己是怎么做出来的

发表于 2022-10-05 18:31:48 回复(0)

Java

Cyan_Mu

两种题解方法+自己的无脑递归三种方法汇总：

package huawei;

/**
 * @author YXQ
 * @create 2022/8/27  17:28
 */

import java.util.*;

/**
 * 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
 * 注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
 * 输入描述：
 * 输入两个int整数
 * 输出描述：
 * 输出结果，int型
 */

/**
 * 用递归能做 但是肯定不是最符合的做法   复杂度太高了
 *
 * ********HashSet<List<Integer>> 能够查重排序后的（5，1，1），（1，5，1），（1, 1, 5）这种重复，只会出现一个。
 */
public class HJ61 {
    static HashSet<List<Integer>> set=new HashSet<>();
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        //法1
//        dfs(n,0,m,new ArrayList<Integer>());
//        System.out.println(set.size());
        //法2
//        System.out.println(dfs(m,n));
        //法3
        System.out.println(putApple(m,n));
    }

    /**
     * 动态规划方法
     * dp[i][j]表示持有i个苹果，有j个盘子可以存放苹果，总共有 dp[i][j]种方法
     * 初始情况：没有苹果，只有一种摆放方法。dp[0][j]=1
     * 递推函数：
     * 1.当i-j<0即苹果数小于盘子数，因为多出来的j-i个盘子不会放苹则dp[i][j]=dp[i][i]
     * 2.当i>=j时：dp[i][j]=dp[i-j][j]+dp[i][j-1]下面的dfs解释了
     * @param m
     * @param n
     * @return
     */
    public static int putApple(int m,int n){
        int[][] dp=new int[m+1][n+1];
        for(int j=0;j<n+1;j++)dp[0][j]=1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(i-j<0){
                    dp[i][j]=dp[i][i];
                }else{
                    dp[i][j]=dp[i-j][j]+dp[i][j-1];
                }

            }
        }
        return dp[m][n];
    }


    /**
     * 递归
     * dfs(m,n)表示把m个苹果放在n个盘子中 分为两种情况
     * 1.至少有一个盘子不放（确定有一个盘子不用）dfs(m,n-1)
     * 2.每个盘子都放苹果，此时从每一个盘子中取出一个苹果，不会影响放法的数量 dfs(m-n,n)
     * 则dfs(m,n)=dfs(m,n-1)+dfs(m-n,n);
     * 在情况1中 当n==1时（盘子为1时）只有一种放法（因为终止条件已经卡到n=1了，所以不用去考虑n=0的情况了）
     * 在情况2中 当m=0时 return 1(0个苹果时 每个盘子都不放 是一种放法)   当m<0时 return 0;
     * @param m
     * @param n
     * @return
     */
    public static int dfs(int m,int n){
        if(m==0||n==1)return 1;
        if(m<0)return 0;
        return dfs(m,n-1)+dfs(m-n,n);
    }

    /**
     * 方法1 递归 递归深度是盘子的数量  递归函数体是为每个盘子放一定数量的苹果
     * 递归结束条件是 盘子完了&&苹果完了
     * @param n
     * @param index
     * @param target
     * @param path
     */
    public static void dfs(int n,int index,int target,List<Integer> path){
        if(index==n){
           if(target==0){
               List<Integer> ans=new ArrayList<>(path);
               Collections.sort(ans);
               if(!set.contains(ans))set.add(ans);
           }
            return;
        }
        for(int i=0;i<=target;i++){
            path.add(i);
            dfs(n,index+1,target-i,path);
            path.remove(path.size()-1);
        }
    }

}

发表于 2022-08-28 15:46:05 回复(1)

Java

炮炮小明

import java.util.Scanner;

/**
 * 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
 * 注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
 *
 *
 * 1、苹果数 < 盘子数，多余的盘子直接舍弃，因为多出来的盘子不可能放的了苹果。
 * m < n : dp[m][n] = dp[m][m]
 * 2、苹果数 >= 盘子数，那么前面盘子都放苹果，‘放到第n个盘子时’，有两种选择
 * 第n个盘子不放苹果，即舍弃第n个盘子：dp[m][n-1]
 * 第n个盘子放苹果，即到第n个盘子为止每个盘子都有苹果，所以只有m-n个苹果可以自由选择放哪些盘子里了：dp[m-n][n]
 * m >= n : dp[m][n] = dp[m-n][n]
 * 3、注意：其中苹果个数为0的dp[0][n]和盘子个数为1的dp[m][1]其放法默认初始化为1
 */
public class HJ61_dp盘子放苹果 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][1]=1;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i]=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];
            }
        }
        System.out.print(dp[m][n]);
    }
}

发表于 2022-08-26 15:36:30 回复(0)

Java

舒渊

10个苹果9个盘子我就始终得不到他的41 我就只能得到40

真奇怪, 所有的可能都列出来了数数还是40 ,这答案有问题还是咋回事, 疯了

发表于 2022-08-19 19:34:47 回复(2)

Java

我悟了

import java.util.Scanner;

public class Main {
    /**
        1、苹果数 < 盘子数，多余的盘子直接舍弃，因为多出来的盘子不可能放的了苹果。
            m < n : dp[m][n] = dp[m][m]
        2、苹果数 >= 盘子数，那么前面盘子都放苹果，‘放到第n个盘子时’，有两种选择
            第n个盘子不放苹果，即舍弃第n个盘子：dp[m][n-1]
            第n个盘子放苹果，即到第n个盘子为止每个盘子都有苹果，所以只有m-n个苹果可以自由选择放哪些盘子里了：dp[m-n][n]
            m >= n : dp[m][n] = dp[m-n][n]
        3、注意：其中苹果个数为0的dp[0][n]和盘子个数为1的dp[m][1]其放法默认初始化为1
    */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(i==0 || j==1) {
                    dp[i][j] = 1;
                    continue;
                }
                if(i<j) {
                    dp[i][j] = dp[i][i];
                } else {
                    // 这里不会出现j-1=0的情况，上面当j=1的时候就已经跳过了
                    dp[i][j] = dp[i][j-1] + dp[i-j][j];  
                }
            }
        }
        System.out.print(dp[m][n]);
    }
}

发表于 2022-07-07 22:33:47 回复(0)

Java

M870RushB

动态规划是真不会，抄的代码

import java.util.Scanner;

public class Main{
    public static int ans(int m, int n){
        if(n == 1 || m == 0)return 1;
        else if(m<n)return ans(m,m);
        else return ans(m, n-1) + ans(m-n, n);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        System.out.println(ans(m,n));
    }
}

发表于 2022-04-21 19:41:54 回复(0)

Java

牛客93863376号

我不懂怎么做，也不知道什么是动态规划，抄评论区动态规划，改了一下

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = Integer.parseInt(sc.next());
            int n = Integer.parseInt(sc.next());
            System.out.println(fib(m, n));
        }
    }

    static int fib(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        return dp(dp, m, n);
    }

    static int dp(int[][] dp, int m, int n) {
        if  (m == 0 || n == 1) {
            return 1;
        }
        // 计算过不再计算
        if (dp[m][n] != 0) {
            return dp[m][n];
        }
        if (n > m) {
            dp[m][n] = dp(dp, m, n - 1);
        } else {
            dp[m][n] = dp(dp, m, n - 1) + dp(dp, m - n, n);
        }
        return dp[m][n];
    }
}

发表于 2022-04-11 14:19:24 回复(0)

Java

牛客625811427号

import java.util.*;
public class Main {
	static int []a=new int[11];
	static int count=0;
	static ArrayList<Integer> ans=new ArrayList<Integer>();
	public static void dfs(int num,int n) {   //num表示剩余的可以放置的苹果数
		if(ans.size()==n+1 ) {
			if(num==0)
				count++;
			return;
		}
		for(int i=0;i<=num;i++) {
			if(i>=ans.get(ans.size()-1)) {
				ans.add(i);
				dfs(num-i,n);
				ans.remove(ans.size()-1);
			}
		}
	}
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int m=in.nextInt();
		int n=in.nextInt();
		ans.add(0);
		dfs(m,n);
		System.out.println(count);
	}

}

发表于 2022-03-24 17:28:37 回复(0)

Java

奥因克

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(calculate(m,n));
        }
    }
    public static int calculate(int m,int n){
        if(m < 0 || n <= 0){
            return 0;
        }
        if(m == 1 || n == 1 || m == 0){
            return 1;
        }
        return calculate(m,n-1)+calculate(m-n,n);
    }
}

发表于 2021-11-30 13:50:19 回复(0)

Java

莱特雷

import java.util.Scanner;

public class Main {
    /*
    解析：
        放苹果情况：（1）有空盘，（2）无空盘
        有空盘理解为：f(m, n) = f(m, n-1)，在n-1个盘上放苹果，一次类推直到n==1，只有1种放法
        无空盘理解为：f(m, n) = f(m-n, n)，在n个盘上放1个苹果，剩下的m-n苹果随意放，直到m<n时，返回0，当m=n，即m-n=0时，返回1
        所以f(m, n) = f(m, n-1) + f(m-n, n);
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            System.out.println(countWays(sc.nextInt(), sc.nextInt()));
        }
    }

    // 动态规划
    public static int countWays(int m, int n) {
        // 额外创建一行作为辅助行
        int[][] dp = new int[m+1][n+1];
        // 初始化（m-n=0时，1种摆法）(n=1, 1种摆法【可省略】)
        for (int j=0; j<n+1; j++) {
            dp[0][j] = 1;
        }
        // 遍历计算（f(m, n) = f(m, n-1) + f(m-n, n)）
        for (int i=1; i<m+1; i++) {
            for (int j=1; j<n+1; j++) {
                dp[i][j] = dp[i][j-1] + (i < j ? 0 : dp[i-j][j]);
            }
        }
        return dp[m][n];
    }
}

发表于 2021-11-12 14:02:07 回复(0)

提交观点

问题信息

动态规划递归

难度：

38条回答 5457收藏 35986浏览

通过挑战的用户

查看代码

我是起名字的天才

2023-03-10 16:22:17
21岁扶墙编程

2023-03-06 23:12:39
奈何笑不了

2023-03-02 10:18:23
加班狗玩代码

2023-02-09 21:29:24
97-Cherry

2023-02-08 17:14:45

放苹果

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题