题解 | #放苹果#

#include <stdio.h>
#include <string.h>
 
int f(int m, int n);
 int main()
{
    int m, n;
     while (scanf("%d %d", &m, &n) != EOF)
    {
        printf("%d\n", f(m, n));
    }
 
    return 0;
}
 
int f(int m, int n)
{
    int ret;
    if (n == 1)
    {
        ret = 1; //m个果放1个盘子 1种
    }
    else if (m == 0)
    {
        ret = 1; //0个果放n个盘子 1种
    }
    else if (m < n)
    {
        ret = f(m,m); 
        //当m<n：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响，
        //即if(n>m) f(m,n) = f(m,m) 问题变成m个苹果，m个盘子的问题。即下面的m>=n的情况.
    }
    else if (m >= n)
    {
        ret = f(m - n, n) + f(m, n - 1); 
        //1.至少有一个空盘f(m,n) = f(m,n-1)；
        //2.一个空盘都没有f(m,n) = f(m-n,n);(即如果所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目.
        //分析则有，总的放苹果的放法数目等于1、2两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n))
    }
 
    return ret;
}