M个苹果放入N个盘子（递归）

题目：

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

输入

每个用例包含二个整数M和N。0<=m<=10，1<=n<=10。

样例输入

7 3

样例输出

8

解法一：

#include<stdio.h>
int count = 0;

void f(int n, int m, int low) {
    if (n == 0) {
        if (m == 0) {
            count++; // 没有苹果也没有盘子，是一种有效的分配方式
        }
        // 如果没有盘子但还有苹果，不增加count
        return;
    }
    for (int i = low; i <= m; i++) {
        f(n - 1, m - i, i); // 下一个盘子从大于等于i个苹果开始
    }
}

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    f(n, m, 0);
    printf("%d", count);
    return 0;
}

解法二：

#include <stdio.h>


int apple(int m, int n)
{
    if (m < 0 ) {
        return 0;
    }

    if (m == 1 || n == 1) {
        return 1;
    }
    return apple(m, n-1) + apple(m-n, n);
}

int main()
{
    int m = 0, n = 0;

    scanf("%d", &m);
    scanf("%d", &n);

    printf("%d", apple(m, n));

    return 0;
}