题目描述

有5只灰太狼和1只喜羊羊被困在了孤岛上，狼可以选择吃草或者吃羊，只能同时有一只狼吃羊，其他的狼当观众。如果有狼选择吃羊，那么吃完以后这只灰太狼会变成美羊羊，剩下的狼可以继续选择吃它或吃草。假设每只狼都很聪明，并且每只狼都贪生怕死，那么喜羊羊会被灰太狼吃掉吗？

思路解析

有些同学看完题目描述大脑已经一片空白了，满脑子都是喜羊羊和灰太狼。题目中的狼有点多，我们由浅入深，慢慢来分析一下这道题。

1. 如果有1只狼，毫无疑问它会选择把羊吃掉，即使吃完以后自己变成了羊，生命并不会受到威胁。这个时候喜羊羊必死。
2. 如果有2只狼，所有的狼都不会选择先吃羊，因为吃完以后自己会变成另一只狼的盘中餐。这个时候喜羊羊可以安心吃草。
3. 如果有3只狼，假设有一只狼把羊吃掉，这个时候岛上就变成了2只狼和1只羊，即步骤2中的情况，成为步骤2中的羊不会死。因为狼比较聪明，已经预判到了这一点，所以动作最快的那只狼可以选择吃羊。这个时候喜羊羊必死。
4. 如果有4只狼，假设有一只狼把羊吃掉，这个时候岛上就变成了3只狼和1只羊，即步骤3中的情况，成为步骤3中的羊必死。因为狼比较聪明，已经预判到了这一点，所以4只狼都只能流口水。这个时候喜羊羊可以安心吃草。
5. 如果有5只狼，假设有一只狼把羊吃掉，这个时候岛上就变成了4只狼和1只羊，即步骤4中的情况，成为步骤4中的羊不会死，因为狼比较聪明，已经预判到了这一点，所以动作最快的那只狼可以选择吃羊。这个时候喜羊羊必死。

所以，有5只灰太狼和1只喜羊羊的情况下，喜羊羊会被灰太狼吃掉。

看到这里聪明的你是不是已经发现了规律？随着灰太狼的数量不断增加，喜羊羊也不断徘徊在生与死的边缘。

这种自下而上的推理方式和我们平时接触的动态规划是不是非常相似，聪明的你能否写出本题的状态转移公式？

最后分享一份算法题目列表，这里既提供了经典题目列表，还提供了对应的高质量题解，让刷题更有效率。非常适合刚刚开始刷题或者为了找工作刷题的同学。

此题目列表包含的知识点是比较全面的。

常用的数据结构： 数组、字符串、链表、二叉树、图、前缀树、集合、映射、栈、队列、堆都有覆盖。

常用的解题方法： 递归、迭代、二分法、回溯、贪心、动态规划、位运算、双指针、模拟、拓扑排序、桶排序、单调栈、深度优先搜索、广度优先搜索都有覆盖。

💖 💖 在线文档 💖 💖

另外题目列表和题解都开源在github上了，欢迎大家提建议。

还有一份硬核后端资料也分享给大家。

另外，想看更多精彩的真题解析可以关注我公众号「溜达虎爱编程」，感谢铁子们捧场了！