3428. 放苹果

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

盘子相对顺序不同，例如 5，1，1 和 1，5，1 算作同一种分法。

输入格式

输入包含多组测试数据。

每组数据占一行，包含两个整数 M 和 N。

输出格式

每组数据，输出一行一个结果表示分法数量。

数据范围

1≤M,N≤10

输入样例：

7 3

输出样例：

8

代码：

/* f(n,m) : 求n个盘子装m个苹果的方案数 找 比 n 小1的规模的方案数，来推出 n规模的方案数 如果找到了 n-1个盘子装 m个苹果的方案数，可能可以推 出n个盘子装m个苹果的方案数 1） M苹果<N 盘子 推出N-M个盘子不装苹果，拿掉这些盘子不影响方案数,剩下 f(n,m)=f( m ,m) 2） M苹果 >= N 盘子 f(n,m)=f(n-1,m)+f( n,m-n ) 分2种情况 (1) 一个盘子不装苹果 f(n,m)=f(n-1,m) (2) 第1种的相反情况 可以用 a&&b&&c&&d&&0 的相反情况 也就是 abcde都为1 每个盘子至少放1个球 每个盘子放1个球，一共放了n苹果，再把剩下的m-n个苹果放到n个盘子里 f(n,m)=f( n,m-n ) 边界情况 第0列 第1行都要初始化为1 */
#include <iostream>
using namespace std;


int f(int n, int m)
{
     // 处理答案
    if (n == 0 || m == 1)
        return 1; // 没有苹果或者是盘子只剩一个
    if (m > n)
        return f(n, n); // 如果盘子数是大于苹果数的，多出来的盘子必定为空
    else
        return f(n, m - 1) + f(n - m, m);
    // else代表盘子数小于等于苹果数，那就有两种情况
    // （1） f(m,n - 1)，有空盘，则至少有1个为空
    // （2） f(m - n,n)，无空盘，则每个盘子至少有一个苹果
}

int main()
{
    
    int n, m;
    while (cin >> n >> m)
    {
    
        cout << f(n, m) << endl;
    }
    return 0;
}