DFS

admin管理员组

文章数量:1794759

DFS

题目：

把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

详解：

最难理解的就是 m>=n的这种情况；
有空盘子时比较好理解，就是去掉一个盘子，就是至少有一个空盘子，因为随着递归的进行，盘子会越来越少。
最难理解的是放满时怎么办，放满时，会有dfs（m-n，n）这一步操作，这一步操作，其实是这样的，就好比7个苹果放在3个盘子里，我们可以先在每个盘子里都放一个苹果，然后把剩下的4个再放在3个都有一个苹果的盘子里。
所以可以把之前每个盘子里放的哪一个苹果当做不存在…嘿嘿嘿，这样就好想了很多。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int DFS(int m,int n)  {if(m == 0 || n == 1)return 1;else if(n > m)return DFS(m, m);elsereturn DFS(m - n, n) + DFS(m, n - 1);
}
int main()  {int t, m, n;scanf("%d", &t);while(t--) {scanf("%d%d", &m, &n);printf("%d\n", DFS(m, n));}return 0;
}

本文标签： DFS