这是左代码上的464，我可以赢，难度是中等的。
标签：“游戏理论DP”，“内存搜索”，“状态压缩”
在“ 100游戏”游戏中，两名玩家轮流选择任何整数从$ 1 $ 1到$ 10 $，累积整数，首先，首先使累积的整数和达到或超过$ 100 $的玩家，这是优胜者。
如果我们将游戏规则更改为“玩家无法重复使用整数”怎么办？
例如，两个玩家可以轮流将整数从$ 1 $ 1到$ 15 $（无需返回），直到累积整数和> = $ 100 $。
给出两个整数（可以在整数池中选择的最大数字）和（累积和不知所措）。如果首先拍摄的球员可以返回，否则它将返回。支持两个球员表现最好的表现。
示例1：
示例2：
示例3：
暗示：
这是游戏理论DP问题。为了方便起见，我们使用$ n $表示$ maxChoosableInteger $，并使用$ t $表示$ desiredTotal $。
由于$ n $的数据范围是$ 20 $，并且每个数字只能选择一次，因此我们可以使用二进制数$状态来表示$ [1，n] $：二进制的范围内选择的数量指示器指示已选择$ 1 $的职位数量，否则意味着尚未选择它。
首先，简单的两个维状态表明它相对容易考虑：定义$ f [state] [k] $是当前选定的$状态$的数量，车轮的数量为$ k $。$。1 $代表能量，$ -1 $的意思不是），其中$ k $从$ 0 $开始，并且可以众所周知是原始回合或后方的第一手。
设计递归功能以实现“内存搜索”。该函数表示当前状态为$状态$，$ tot $，对应于累积积累，$ k $表示车轮的数量，并且通过判断它是否为$ 1 $来了解最终答案。
在转移过程中，如果您找到当前的决定，它可以直接积累并超过$ t $，这表明当前的一轮球员获胜；或者，如果当前的决定可能导致下一轮的失败，那么当前的回合球员也将获胜，否则当前的球员当前将成为玩家。
代码：
进一步发现，如果可以优化车轮的数量，则可以有效地减少一半的计算。我们将状态定义调整为：定义$ f [state] $是当前状态是$状态，“当前第一手”可以赢（$ 1 $代表第一手的代表”（$ 1 $代表代表性，$ -1 $表示不是）。
同时，递归函数为$ int dfs（int state，int tot）$，通过判断它是否为$ 1 $，可以从最终答案中获取最终答案。
请注意，此处调整的重点是“继任者的原始回合以及原始回合的成功获胜”的记录“当前的回合发射和当前的回合胜利”。
代码：
这是我们“通过Leetcode”系列的第一篇文章。该系列始于2021/01/01。从开始开始时的起始代码开始，总共有1916年的问题。该主题已经完成。
在这一系列文章中，除了解释问题 - 解决想法之外，还将尽可能多地提供最简洁的代码。如果涉及通信，将有相应的代码模板。
为了使学生更容易在计算机上调试和提交代码，我建立了一个相关的仓库：https：//github.com/sharingsource/logicstack-letcode。
在仓库地址中，您可以看到一系列文章的解释链接，一系列文章的相应代码，leetcode的原始链接以及其他首选解决方案。
原始：https：//juejin.cn/post/7100389488643276808