HJ61. 放苹果

刷题

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

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

输入描述：输入两个int整数
输出描述：输出结果，int型

示例：

输入：7 3
输出：8

public class HJ61_放苹果 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            //dp[i][j]表示i个苹果放到j个盘子里的不同分法数
            int[][] dp = new int[m+1][n+1];
            for (int i=1; i<=n; i++) {
                dp[0][i] = 1;//没有盘子只有苹果，1种分法
            }
            for (int i=1; i<=m; i++) {
                for (int j=1; j<=n; j++) {
                    if (i < j){
                        //苹果<盘子，多出来的盘子其实没用，也相当于dp[i][i]
                        dp[i][j] = dp[i][j-1];
                    }else{
                        //苹果>=盘子，有两种情况：1.有空盘；2.没有空盘
                        dp[i][j] = dp[i][j-1] + dp[i-j][j];
                    }
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}