题解 | #放苹果#

本题考查递归，简化问题成子问题，要么少放一个盘子里，要么就每个盘子都放一个先。注意没有苹果也可以算一种情况，

#include <iostream>
using namespace std;

int plans(int apples, int plates){
    // 若无苹果或盘子,注意无苹果可分也算一种方案
    if(apples < 0 || plates <= 0)
        return 0;
    // 若只有一个苹果或只有一个盘子
    else if(apples == 1 || plates == 1)
        return 1;
    // 若苹果和盘子都多于1，那么该问题可以看作两个子问题的加和
    // 子问题1：一个盘子不放，放在其他盘子上
    // 子问题2：每个盘子放1个先
    else
        return plans(apples, plates-1) + plans(apples-plates, plates);
}

int main() {
    int apples, plates = 0;

    cin >> apples >> plates;

    int plan = plans(apples, plates);

    cout << plan << endl;
}
// 64 位输出请用 printf("%lld")