题解 | HJ61#放苹果#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer m = sc.nextInt();//苹果数量
        Integer n = sc.nextInt();//盘子数量
        Integer count = solve(m,n);
        System.out.println(count);
    }
    //动态规划 解题
    public static Integer solve(Integer m,Integer 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];
    }
/*  //递归 解题
    public static Integer solve(Integer m,Integer n){
        if (m==1||m==0||n==1){//0个苹果，n个盘子。或者 m个苹果，1个盘子。
            return 1;
        }else if(m<n){//苹果数量 < 盘子的数量。
            // 增加空盘子，不能增加解法的数量，所以按照m个盘子。
            // 调用solve函数 计算：
            // 将M个苹果放入M个盘子的解法数量
            return solve(m,m);
        } else {//else if (m>n)   苹果的数量 > 盘子的数量。
            // 1.保证每个盘子都有1个苹果，然后将剩下的，M-N个苹果放入N个盘子。
            // 2.只有一个盘子空着，然后将M个苹果放入N-1个盘子。
            // 分别调用solve函数 计算：
            // 将M-N个苹果放入N个盘子的解法数量
            //和将M个苹果放入N-1个盘子的解法数量
            return solve(m-n,n)+solve(m,n-1);

            //因为空盘子的数量不影响分法数量。所以按照一个空或者都满来递归计算。
        }
    }
    */
}