放珠子

coding>C++>Java
1.3k 词

题目描述

把M个同样的珠子放在N个同样的盒子里，允许有的盒子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入

第一行是测试数据的数目t$（0 <= t <= 20）$。以下每行均包含二个整数M和N，以空格分开。$0<=M$，$N<=25$。

输出

对输入的每组数据M和N，用一行输出相应的K。

样例输入

1
2
1
7 3

样例输出

1
8

题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'
ll dp[26][26];

/**
 * 把m个苹果 放入N个盘子
 * @param m 苹果数量
 * @param n 盘子数量
 * @return 不考虑顺序的方案数
 */
ll f(int m, int n) {
    if (dp[m][n] != 0)return dp[m][n];
    if (m <= 1  n == 1)return dp[m][n] = 1;//递归终点
    if (m < n)return dp[m][n] = f(m, m);//必然会存在n-m个以上的空盘子
    return dp[m][n] = f(m, n - 1)//至少有一个空盘子方案
                      + f(m - n, n);//没有一个空盘子的方案

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int m, n;
        cin >> m >> n;
        cout << f(m, n) << endl;
    }
    return 0;
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
 
 
public class Main {
  public static void main(String []ages)
  {
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  while(n--!=0)
  {
  int a=sc.nextInt();
  int b=sc.nextInt();
  System.out.println(count(a,b));
  }
  }
  static int count(int apple,int plant)
  {
  if(apple==0plant==1)
  return 1;
    if(plant>apple)
    {
    return count(apple,apple);
    }
    else
    {
    return (count(apple,plant-1)+count(apple-plant,plant));
    }
  }
}