放苹果

题目描述

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

输入

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

样例输入

7 3

样例输出

8

/**

• 计算放苹果方法数目

• 输入值非法时返回-1

• 1 <= m,n <= 10

• @param m 苹果数目

• @param n 盘子数目数

• @return 放置方法总数

*/

public static int count(int m, int n)

输入描述:

输入两个int整数

输出描述:

输出结果，int型

示例1

输入
7 3
输出
8

思路

链接：https://www.nowcoder.com/questionTerminal/bfd8234bb5e84be0b493656e390bdebf
来源：牛客网

/*

放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。

令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。

1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可

2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上

即求(m-n，n)

综上所述：

(m，n)=(m,n-1)+(m-n,n);

*/

#include<iostream>
using namespace std;
#include<string>
#include<vector>
int putapples(int m, int n);
int main() {
    int num1,num2;
    while (cin>>num1>>num2)
    {
        int result=putapples(num1, num2);
        cout << result << endl;
    }
}
//m 苹果，n 盘子
int putapples(int m, int n) {
    //没有苹果
    if (m < 0) {
        return 0;
    }
    /*
    m==1,只有1个苹果
    n==1,只剩下一个盘子
    */
    if (m == 1 || n == 1) {
        return 1;
    }
    /*
    1个空盘子，没有空盘子。一个空盘子的对立面是一个空盘子都没有。
    putapples(m, n - 1) 只有1个空盘子
    putapples(m-n,n) 一个空盘子都没有
    */
    return putapples(m, n - 1) + putapples(m-n,n);
}