放苹果

放苹果

解析

参考牛客网解析：

难点:
当苹果大于盘子时,(这是大前提,注意哦) 我们怎么确定有多少种放法. 此时我们考虑了分类.
思路来源: 分类计数原理:完成一件事情有n类办法,那么完成这件事共有N=m₁+m₂+…+m _n 种不同的方法.
分类:
分为有空盘和没有空盘的两种情况.
检查分类
1. 完备性
是否囊括所有情况, 所有的放苹果方法,要么有空盘,要么没有空盘.
2. 分类是否重复
一类有空盘,一类无空盘,不会重复.
分类后,我们如何操作可以保证满足分类条件
1. 保证有空盘
单独拿一个盘子不放,此时的情形,对于放法数而言,是不是相当于f(apple, plate-1).
2. 保证没有空盘
首先每个盘子放一个苹果,这样不就可以保证了,此时的情形,对于放法数而言,是不是相当于f(apple-plate,plate)

代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(dp(m, n));
    }

    static int dp(int m, int n) {
        if (m == 0 || n == 1) {
            return 1;
        } else if (n > m) {
            return dp(m, m);
        } else {
            return dp(m, n - 1) + dp(m - n, n);
        }
    }
}