题解 | # D Enjoy the game

题目分析

算法选择： 多阶段决策问题--->Dp

核心规律：斐波那契数与必败态

F(1)=1 ， F(2)=2 ， F(k)=F(k−1)+F(k−2) （ k≥3 ），即数列：1, 2, 3, 5, 8, 13, 21, ...

斐波那契数列的核心性质：任意斐波那契数 (F(k)) 不能被拆分为两个不相邻的斐波那契数之和，且 (F(k) = F(k-1) + F(k-2))。

这个性质决定了：若当前卡牌数是斐波那契数 (F(k))，先手拿 x 张（(1 \leq x \leq F(k)-1)），后手总能拿 (F(k-2) - x) 或 (F(k-1) - x) 张，使剩余卡牌数仍为斐波那契数，逐步缩小范围，最终后手拿最后一张牌

例 1：(n=2)（斐波那契数 (F(2))）先手必须拿 1 张（最多拿 (2-1=1) 张），剩余 1 张由后手拿走，后手获胜→输出 Alice（正确）。

用例 2：(n=3)（斐波那契数 (F(3))）先手拿 1 张→剩余 2 张，后手最多拿 1 张（跟上一步先手拿的数量），后手拿 1 张，剩余 1 张，先手只能拿 1 张→后手拿最后 1 张获胜；先手拿 2 张→剩余 1 张，后手直接拿完获胜→无论怎么拿，先手必败→输出 Alice。

用例 3：(n=4)（非斐波那契数）先手拿 1 张→剩余 3 张（斐波那契数，后手陷入必败态）；后手面对 3 张，无论拿 1 或 2 张，先手都能拿完剩余牌→先手必胜→输出 Bob。

用例 4：(n=5)（斐波那契数 (F(4))）先手拿 1 张→剩余 4 张，后手拿 3 张→剩余 1 张，先手只能拿 1 张→后手获胜；先手拿 2 张→剩余 3 张，后手拿 1 张→剩余 2 张，先手最多拿 1 张→后手拿完获胜；先手拿 3 张→剩余 2 张，后手最多拿 3 张→直接拿完获胜→先手必败→输出 Alice。

```int fib(int n)
{
    if(n==1||n==2) return 1;
    else return (fib(n-1)+fib(n-2));
    
}//斐波那契递归公式