Java题解 | HJ61 #放苹果#

描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围： 0≤m≤10 ， 1≤n≤10 。

输入描述：
输入两个int整数

输出描述：
输出结果，int型

示例1

输入：
7 3

输出：
8

解法：递归

设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，

• 当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)　　
• 当n<=m：不同的放法可以分成两类：
  • 1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
  • 2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).
• 而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)

递归出口条件说明：

• 当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
• 当没有苹果可放时，定义为１种放法；

递归的两条路，

• 第一条n会逐渐减少，终会到达出口n==1;
• 第二条m会逐渐减少，因为n>m时，我们会return f(m,m)　所以终会到达出口m==0

/**
 * Welcome to https://waylau.com
 */
package com.waylau.nowcoder.exam.oj.huawei;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * HJ61 放苹果.
 * 描述：把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
 * 注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
 * 数据范围： `0≤m≤10` ， `1≤n≤10` 。
 * 输入描述：
 * 输入两个int整数
 * 输出描述：
 * 输出结果，int型
 * 示例1
 * 输入：
 * 7 3
 * 输出：
 * 8
 * 
 * @since 1.0.0 2022年8月27日
 * @author <a href="https://waylau.com">Way Lau</a>
 */
public class HJ061PutApple {

    public static void main(String[] args)
            throws IOException {
        // 输入
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");

        int appleNamber = Integer.valueOf(in[0]);
        int plateNamber = Integer.valueOf(in[1]);

        // 输出
        System.out
                .println(getWays(appleNamber, plateNamber));

        // 关闭
        br.close();
    }

    private static int getWays(int appleNamber,
            int plateNamber) {

        // 只有1个盘子或者只有1个苹果，那只有1种分发
        if (appleNamber == 1 || plateNamber == 1) {
            return 1;
        }

        // 没有也是1种分发
        if (appleNamber == 0) {
            return 1;
        }

        // 没有盘子就分不成了
        if (plateNamber == 0) {
            return 0;
        }

        // 当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。
        // 即`if(n>m) f(m,n) = f(m,m)`
        if (plateNamber > appleNamber) {
            return getWays(appleNamber, appleNamber);
        }

        // 当n<=m：不同的放法可以分成两类：
        // 1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
        // 2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).
        // 而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)
        return getWays(appleNamber, plateNamber - 1)
                + getWays(appleNamber - plateNamber,
                        plateNamber);
    }
}

参考引用

• 本系列归档至https://github.com/waylau/nowcoder-exam-oj
• 《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
• 《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html