LeetCode 464. 我能赢吗（状态压缩+记忆化递归 / 博弈）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。

示例： 输入： maxChoosableInteger = 10 desiredTotal = 11 输出： false 解释： 无论第一个玩家选择哪个整数，他都会失败。 第一个玩家可以选择从 1 到 10 的整数。 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利. 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/can-i-win
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：LeetCode 486. 预测赢家（博弈DP）

class Solution {unordered_map<int,bool> m; public:bool canIWin(int maxChoosableInteger, int desiredTotal) {if((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal)return false;//总和不够return win(maxChoosableInteger, desiredTotal, 0, 0);}bool win(int maxChoosableInteger, int desiredTotal, int point, int state) {if(m.find(state) != m.end())return m[state];//重复的状态，直接读取for(int i = 1; i <= maxChoosableInteger; i++){if(((state>>i)&1)==0){ // 该二进制位为0 表示没有拿过该数if(point+i >= desiredTotal)return true;int newstate = state | (1<<i);//新的状态，该位为1，用过了if(!win(maxChoosableInteger, desiredTotal, point+i, newstate))return m[state] = true;//上一个人在 newstate 下不能赢，那我在 state 状态下能赢}}return m[state] = false;} };

508 ms 17.5 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的LeetCode 464. 我能赢吗（状态压缩+记忆化递归 / 博弈）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。