题解 | #放苹果#

/*
 * https://blog.nowcoder.net/n/c9bc6821b3cd469b9cdb56469809e946
 */
#include <stdio.h>

int cal(int m, int n)
{
    //printf("m[%d]  n[%d] ", m, n);
    if ((m <= 1) || (n == 1)) {   /* 特殊情况1，只有一个盘子或者只有一个苹果，或者没有苹果 */
        return 1;
    } else if (m < n) {   /* 特殊情况2： 问题转换，苹果比盘子少， cal(m,m)和cal(m,n)的结果一样，因为始终有一个空盘子*/
        return cal(m,m);
    } else {
        /* 正常情况，分两部分，1，至少一个盘子为空， 全部不为空，求和即得到全集
         * 其中至少一个盘子不为空，可以看成1，2，3.。。个盘子不为空，
          *多个盘子为空可以看成是1个盘子为空的特殊情况，包含关系，所以只有一项 cal(m,n-1)。
         */
        return cal(m,n-1) + cal(m-n, n);
    }
}

int main() {
    int m, n;
    int sum = 0;

    while(scanf("%d %d", &m, &n) != EOF) {

        sum = cal(m, n);

        printf("%d", sum);
    }


    return 0;
}