练47.4 小明吃苹果

解题思路

设f(r)为剩r个苹果时的吃法。妹妹可选吃1或2个（不能超过剩余），然后姐姐若仍有苹果再吃1个。对两种妹妹选择分别递归到新剩余量，f(0)=1表示一种已完成方案。

正确性说明

按妹妹当天选择分类，两个分支互斥并覆盖全部可能；姐姐动作确定，后续方案数恰是更小状态f(left)，所以各分支求和完整且不重复。

易错点

余1个时不能选择吃2个；姐姐吃苹果不产生选择。

复杂度

时间O(n)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> f(n + 1);
    f[0] = 1;
    for (int r = 1; r <= n; r++)
        for (int eat = 1; eat <= 2 && eat <= r; eat++) {
            int left = r - eat;
            if (left > 0)
                left--;
            f[r] += f[left];
        }
    cout << f[n] << "\n";
    return 0;
}