题解 | #放苹果#

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

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

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

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

综上所述： f(m，n)=f(m,n-1)+f(m-n,n);

#include <iostream>
using namespace std;

int AppleSet(int m, int n)
{
    int nums;
    if(m < 0 || n < 0)
        nums = 0;
    if(m == 0 || n == 0)  //0个苹果或者0个盘子也要算一种！
        nums = 1;
    if(m == 1 || n == 1)
        nums = 1;
    if(m>1 && n>1)
        nums = AppleSet(m, n-1) + AppleSet(m-n, n);
    
    return nums;
}
int main()
{
    int m,n;
    while(cin>>m>>n)
        cout<<AppleSet(m,n);
    
    return 0;
}