题解 | #放苹果#

所有的放法：fun(m,n) = 盘子中至少有一个苹果的情况总和(这里有个假设条件，苹果数大于盘子数)+至少有一个是空盘的情况
盘子中至少有一个苹果的方法: 盘子中至少有一个苹果，则剩余m-n个苹果。所以这种情况研究的是 这m-n个苹果的放法的总和，即：fun(m-n,n) 至少有一个是空盘的方法：即 m个苹果最多放到n-1个盘子里的情况总和：fun(m,n-1)

如果有疑惑，看下至少有一个苹果的情况：7个苹果，5个盘子 即：f(2,5)，如果没有出递归，则这种情况下，苹果的放法都是一样的(（5，1，1）和（1，5，1）被视为是同一种分法)，即fun(2,5)=fun(2,4)=fun(2,3)=fun(2,2)，因为2个苹果放到2个，3个，或者4个、或者5个盘子里的情况是一样的，即2中放法：1、1；2、0

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int appleNum = sc.nextInt();
            int pNum = sc.nextInt();
            System.out.println(function(appleNum, pNum));
        }
        sc.close();
    }

    public static int function(int appleNum, int pNum) {
        if (appleNum == 0 || pNum == 1) {//递归出口
            return 1;
        } else {
            if (appleNum >= pNum) {//苹果数大于等于盘子数时
                return function(appleNum - pNum, pNum) + function(appleNum, pNum - 1);
            } else {
                return function(appleNum, pNum - 1);
            }
        }
    }
}