题解 | #放苹果#

个人思路，仅供参考，递归解法：

一、确定终止条件，用递归肯定到最后得有结束条件吧。

    由于是两个变量，我们看看这两个变量最简单的时候是什么结果？
        （1）m=0或m=1：没有苹果或只有一个苹果，那方式只有一种
        （2）n=1：只有一个盘子，那苹果只能放在这一个盘子上，方式也只会有一种

二、确定递归体（本题难点），也就是怎么把复杂的m个苹果，n个盘，转化成更简单的情况。

    首先是需要往简单的靠，那就考虑m 和 n ，跟 m-1 和 n-1到底有什么关系？假设F(m，n)就是求m个苹果n个盘情况下的方式总数，那现在就是考虑 F(m，n)和F(m-1，n)、F(m，n-1)有什么关系？

    1、【m在变】 一开始我是在想，假设不考虑盘子变化，m个苹果去分配，跟m-1个苹果去分配有什么关联？m中多出来的一个苹果如果在m-1中分配？
            这个情况我没想明白，看下一个。
    2、【n在变】 假设不考虑苹果变化，n个盘子和n-1个盘子有什么关联呢？这里有两个考虑方向，简单-->复杂，复杂-->简单。
        （1）n-1个盘子加了一个盘子，变成n个盘子，分配方式如何变化？
        （2）n个盘子拿走了一个盘子，变成n-1个盘子，分配方式如何变化？
            上面两种思考的方向，我觉得对推导递归体可能会有不同的效果吧。第一个一般是写动态规划代码的考虑，第二个就比较容易联想递归的方式。 
            拿走了一个盘子，相当于这个盘子不存在，也就是说，n个盘子，保证1个盘子是空的，剩下盘子去分配m个苹果。
            【关键点】来了，F(m，n)可以分成两种情况，存在一个空盘子，不存在空盘子。
            1）m个盘子中存在一个空盘子，那么分配方式有多少种？答案是F(m,n-1)
            2）m个盘子中不存在空盘子，那么分配方式有多少种？答案是F(m-n,n) ，
                因为要考虑不存在空盘子，那每个盘子中不就必须先分配1个吗？也就是能给我们分配的只要m-n个了。
            最终结果出来了，F(m,n) = F（m,n-1） + F (m-n,n) 
     补充：还有一个情况，盘子太多了，一定有空盘，那分配方式我们可以直接省略空盘，直接考虑盘子跟苹果数一样的情况下的分配方式。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");

        int m = Integer.parseInt(s[0]);
        int n = Integer.parseInt(s[1]);

        System.out.println(f(m,n));
    }

    public static int f(int m,int n){
        //确定终止条件
        if ( m == 0 || m == 1 || n == 1){
            return 1;
        }
        //确定递归体
        if (n > m){
            return f(m,m);
        }
        return f(m-n,n) + f(m,n-1);
    }
}