[关闭]
@yexiaoqi 2022-05-20T08:39:14.000000Z 字数 602 阅读 370

HJ61. 放苹果

刷题


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

数据范围:0≤m≤10,1≤n≤10。

输入描述:输入两个int整数
输出描述:输出结果,int型

示例

输入:7 3
输出:8

  1. public class HJ61_放苹果 {
  2. public static void main(String[] args){
  3. Scanner sc = new Scanner(System.in);
  4. while(sc.hasNext()){
  5. int m = sc.nextInt();
  6. int n = sc.nextInt();
  7. //dp[i][j]表示i个苹果放到j个盘子里的不同分法数
  8. int[][] dp = new int[m+1][n+1];
  9. for (int i=1; i<=n; i++) {
  10. dp[0][i] = 1;//没有盘子只有苹果,1种分法
  11. }
  12. for (int i=1; i<=m; i++) {
  13. for (int j=1; j<=n; j++) {
  14. if (i < j){
  15. //苹果<盘子,多出来的盘子其实没用,也相当于dp[i][i]
  16. dp[i][j] = dp[i][j-1];
  17. }else{
  18. //苹果>=盘子,有两种情况:1.有空盘;2.没有空盘
  19. dp[i][j] = dp[i][j-1] + dp[i-j][j];
  20. }
  21. }
  22. }
  23. System.out.println(dp[m][n]);
  24. }
  25. }
  26. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注