MIOJ #35 分糖果

描述

将 M 个同样的糖果放在 N 个同样的篮子里,允许有的篮子空着不放,共有多少种不同的分法? 比如,把 7 个糖果放在 3 个篮子里,共有 8 种分法(每个数表示篮子中放的糖果数,数的个数为篮子数): 1 1 5 1 2 4 1 3 3 2 2 3 2 5 0 3 4 0 6 1 0 7 0 0

注意:相同的分布,顺序不同也只算作一种分法,如 7 0 0、0 7 0 和 0 0 7 只算作一种。

输入

输入包含二个正整数 M 和 N,以(,)分开,M 表示有几个同样的糖果,N 表示有几个同样的篮子 M与N范围:1 <= M,N <= 100。

输出

输出一个正整数 K,表示有多少种分法。

输入样例

7,3

输出样例

8

AC代码:

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

int calc(int m,int n)
{
    if(m== 0 || n==1)
    {
        return 1;
    }
    //当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
    //当没有苹果可放时,定义为1种放法;
    //递归的两条路,第一条n会逐渐减少,终会到达出口n==1;
    //第二条m会逐渐减少,因为n>m时,我们会return f(m,m) 所以终会到达出口m==0.
    if(m < n)
    {
        return calc(m,m);
    }
    else
    {
        return calc(m-n,n)+calc(m,n-1);
        //所有篮子放满和有一个篮子空的情况
        //放满的时候分法和每个篮子拿去一个糖果相同
        //有一个篮子空的时候相当于和这个篮子不存在的时候的分法相同
    }
}


int main()
{
    int m = 0;
    int n = 0;
    while(cin>>m)
    {
        cin.get();
        cin>>n;
        cout<<calc(m,n)<<endl;
    }
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注