2018-3-15
这道题目老早就见过，但是在这一次写的时候又出现了 一个问题，我知道如果第n个盘子不用的话就等同于m个苹果放在n-1个盘子中，但是如果我们第n个盘子用了呢？那我们就得把所有的n个盘子里面都放一个才可以，因为我们这个是不考虑顺序的，我们必须保证得到的两个是完全没有交集的，我们不能把相同的情况计算多遍！如果说我们没有把n个盘子都放一个的话，那么我们在f(m,n-1)里面也会出现空的盘子，那可能就出现重复的情况了。
#include<iostream>
using namespace std;
int dfs(
int m,
int n){
if (m<
0||n<
0){
return 0;
}
if (m==
1||n==
1||m==
0||n==
0)
return 1;
return dfs(m,n-
1)+dfs(m-n,n);
}
int main(){
int t;
cin>>t;
while (t--){
int m,n;
cin>>m>>n;
cout<<dfs(m,n)<<endl;
}
return 0;
}
