放苹果
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 30284 | Accepted: 19098 |
Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input
1
7 3
Sample Output
8
分析：简单的DFS，可以把问题想象成把一个整数M分解成N个数相加，其中符合加法交换律的是一种情况。为保证不重复（即不会出现加法交换律的情况出现），可以令分解的N个数呈非递增（或非递减）顺序排列，所以下面的递归函数里，有一个参数是前一个数的大小，在本次递归里分配的数要不大于前一个数的大小。
Java AC 代码
import java.util.Scanner;
public class Main {
static int apples;
static int plates;
static int plans;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int testNumber = sc.nextInt();
for(int i = 1; i <= testNumber; i++) {
apples = sc.nextInt();
plates = sc.nextInt();
plans = 0;
dfs(apples, plates, apples + 1);
System.out.println(plans);
}
}
/**
*
* @param leftApples 剩余的苹果数
* @param leftPlates 剩余的盘子数
* @param pre 前一个盘子放的苹果数。要保证当前盘子放的苹果数小于前一个盘子放的苹果数，这样可以避免重复（当然也可以把顺序反过来放）
*/
public static void dfs(int leftApples, int leftPlates, int pre) {
if(leftApples == 0 && leftPlates >=0) { //苹果没了，但盘子还有或恰好没有，则方案数加1
plans ++;
return;
}
if(leftPlates <= 0)
return;
for(int i = leftApples; i > 0; i--) {
if(i > pre) //如果当前盘子要放的苹果数大于前一个盘子的苹果数，则跳过
continue;
findPlans(leftApples - i, leftPlates - 1, i);
}
}
}