题意：

将M个相同苹果放在N个相同的盘子里，盘子可以为空，求方案数。

思路：

0. 边界条件：没有苹果或者只有一个盘子的时候，方案数为1
1. 若n>m,那就算每个苹果占一个盘子也最多只能占有n个盘子。f(m,n)=f(m,m);
2. 对其余情况f(m,n)，分为放满盘子和不放满盘子两种情况。

① 若放满盘子，则可以将所有盘子的苹果各拿掉一个，方案数不变。f1(m,n)=f(m-n,n)

② 若不放满盘子，则可以把空盘子直接拿掉一个再做考虑f2(m,n)=f(m,n-1)

所以有f(m,n)=f(m-n,n)+f(m,n-1)

煎蛋的戴马：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N,M;
int d[55][55];

int main()
{
    for(int i=0;i<=50;i++)
        for(int j=1;j<=50;j++)
        {
            if(j==1||i==0) d[i][j]=1;
             else if(i<j) d[i][j]=d[i][i];
            else d[i][j]=d[i-j][j]+d[i][j-1];
        }
    int t,m,n;
    cin>>t; 
    while(t--)
    {
        cin>>m>>n;
        cout<<d[m][n]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int t,m,n;
int ans[15][15];
int main(){
	for(int i=0;i<=10;i++)for(int j=1;j<=10;j++){
		if(j==1||i==0)ans[i][j]=1;
		else if(i<j)ans[i][j]=ans[i][i];
		else ans[i][j]=ans[i-j][j]+ans[i][j-1];
	}
	cin>>t;
	while(t--){
		cin>>m>>n;
		cout<<ans[m][n]<<endl;
	}
	return 0;
}

题目大意

把 $m$ 个同样的苹果放在 $n$ 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

思路

这题可以用递推或者递归。

• 边界条件：没有苹果或者只有一个盘子的时候，方案数为 $1$。
• 若 $n>m$，那就算每个苹果占一个盘子也最多只能占有 $n$ 个盘子。
• 对于其他的，分为放满盘子和不放满盘子两种情况即可。

代码1（递归）

#include <bits/stdc++.h>
using namespace std;

int T, a, b;

int f(int m, int n)
{
	if (n == 1 || m == 0 || m == 1) return 1;
	if (n > m) return f(m, m);
	return f(m, n - 1) + f(m - n, n);
}

int main()
{
	cin >> T;
	while (T--)
	{
		cin >> a >> b;
		cout << f(a, b) << endl;
	}
	return 0;
}

代码2（递推）

#include <bits/stdc++.h>
using namespace std;

int T, a, b, f[15][15];

int main()
{
	for (int m = 0; m <= 11; m++)
	{
		for (int n = 1; n <= 11; n++)
		{
			if(m == 0 || n == 1 || m == 1) f[m][n] = 1;
			else if(n > m) f[m][n] = f[m][m];
			else f[m][n] = f[m][n - 1] + f[m - n][n];
		}
	}
	cin >> T;
	while (T--)
	{
		cin >> a >> b;
		cout << f[a][b] << endl;
	}
	return 0;
 } 

#include<iostream>
using namespace std;
long long f(int m,int n){
	if(m==1||n==1||m==0) return 1;//只有一个苹果了，没苹果了，只有一个盘子了都是一种 
	if(n>m) return f(m,m);//盘子比苹果多，考虑最优也只能放满n个，剩下的0对方法数无影响，直接 return f(n,n)
	else return f(m,n-1)+f(m-n,n);//拿走一个盘子放+先全部放一个打底再在其基础上放 
}
int apple;
int plate;
int t;
int main(){
	cin>>t;
	while(t--){
		cin>>apple>>plate;
		cout<<f(apple,plate)<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int t,m,n;
int ans[15][15];
int main(){
	for(int i=0;i<=10;i++)for(int j=1;j<=10;j++){
		if(j==1||i==0)ans[i][j]=1;
		else if(i<j)ans[i][j]=ans[i][i];
		else ans[i][j]=ans[i-j][j]+ans[i][j-1];
	}
	cin>>t;
	while(t--){
		cin>>m>>n;
		cout<<ans[m][n]<<endl;
	}
	return 0;
}

#include<iostream>
#define is =
#define main int main()
using namespace std;
main{
	int get();//in data
	int t is get();//look at define
	while(t--){
		int m is get(),n is get();
		int f(int,int);//recursion
		cout<<f(m,n)<<"\n";
	}
}
int get(){
	int a;
	cin>>a;
	return a;
}
int f(int m,int n){
	if(!m)
	return 1;
	if(n==1)
	return 1;
	if(m<n)
	return f(m,m);//special
	if(m>=n)
	return f(m,n-1)+f(m-n,n);//main
}