- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- int T,n,m;
- int solve(int m,int n){//m 个苹果 n 个盘子
- if(m<=1||n<=1) return 1;// 边界条件
- if(m<n) return solve(m,m);// 苹果比盘子少 等价于把 m 个苹果放入 m 个盘子的方案数
- else return solve(m,n-1)+solve(m-n,n);
- /* 否则 等于有一个盘子空着不放的方案 (有空盘) +
- 把所有盘子都铺上一层苹果后用剩下的苹果放盘子的方案 (没有空盘)*/
- }
- int main(){
- scanf("%d",&T);
- while(T--){
- scanf("%d%d",&m,&n);
- printf("%d\n",solve(m,n));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2949975.html