九度OJ 1160：放苹果 （DFS）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：998

解决：680

题目描述：

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

输入：

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

输出：

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

样例输入：

1

7 3

样例输出：

8

来源：

2011年北京大学计算机研究生机试真题

思路：

DFS可解。

由于盘子是一样的，不能用组合数学中的组合数解。

代码：

#include <stdio.h>

#define T 20

int apple(int m, int n, int max)

{

    if (m < 0)

        return 0;

    if (n == 1 && m > max)

        return 0;

    if (n == 1 && m <= max)

        return 1;

    int sum = 0;

    for (int i=max; i>=0; i--)

        sum += apple(m-i, n-1, i);

    return sum;

}

int main(void)

{

    int t, i;

    int m[T], n[T];

    int sum;

    while (scanf("%d", &t) != EOF)

    {

        for(i=0; i<t; i++)

        {

            scanf("%d%d", &m[i], &n[i]);

            sum = apple(m[i], n[i], m[i]);

            printf("%d\n", sum);

        }

    }

    return 0;

}

/**************************************************************

    Problem: 1160

    User: liangrx06

    Language: C

    Result: Accepted

    Time:0 ms

    Memory:912 kb

****************************************************************/