题解 | #放苹果#

放苹果
算法知识视频讲解
简单 通过率：43.44% 时间限制：1秒 空间限制：32M
知识点
递归
动态规划
题目
题解(31)
讨论(193)
排行
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
题目描述

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

数据范围：0<=m<=10，1<=n<=10。
本题含有多组样例输入。

输入描述：
输入两个int整数

输出描述：
输出结果，int型

示例1
输入：
7 3
复制
输出：
8

#include <iostream>
using namespace std;


/*
* 递归
* 思想：设置getSums(m,n);，苹果为m,盘子为n。
* 当盘子n>苹果m，则一定有n-m个盘子是空着，因此不会影响苹果放在盘子的种类，即getSums(m,n) = getSums(m,n)；
* 当盘子n<=苹果m：
*   1. 至少有一个盘子是空的，则getSums(m,n) = getSums(m,n-1)
    2. 每个盘子都有苹果，则拿走n-m个苹果不影响结果，getSums(m,n) = getSums(m-n,n)
  即getSums(m,n) = getSums(m,n-1) + getSums(m-n,n)
* 递归条件出口：
    当苹果m为0，则盘子上都是空的，即输出为1；
    当盘子为1，则所有苹果都放在一个盘子上，即输出为1；
*/
int getSums(int m, int n) 
{
    if(m == 0 || n ==1) {
        return 1;
    }

    if(n > m) {
        return getSums(m,n-1);
    } else {
        return getSums(m,n-1) + getSums(m-n,n);
    }
}

int main()
{
    int m,n;
    while(cin>>m>>n) {
        int nums = 0;
        nums = getSums(m, n);
        cout<<nums<<endl;
    }
}