跳转至

LeetCode: 464. 我能赢吗

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),从而取得胜利.
同样地,第一个玩家选择任意其他整数,第二个玩家都会赢。

2、解题思路

  • 首先判断边界条件
  • 如果目标小于等于最大值,先手一定True
  • 如果所有数值加和小于目标值,一定是False
  • 递归判断,同时记住历史状态
  • 当前数字作为先手,如果已经能够得到目标值,返回True
  • 如果不能得到,当前值记录为已使用,并且对手使用所有的数字都不能得到胜利,那么当前数字先手肯定是胜利
class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:


        if maxChoosableInteger >= desiredTotal:
            return True
        if (maxChoosableInteger + 1) * maxChoosableInteger // 2 < desiredTotal:
            return False
        stat = {}

        def dfs(cur_stat, maxChoosable, target):
            res = False
            if cur_stat in stat:
                return stat[cur_stat]
            for i in range(1, maxChoosable + 1):
                if 1 << i & cur_stat:
                    continue

                if i >= target:
                    res = True
                else:
                    res = not dfs(cur_stat | (1 << i), maxChoosable, target - i)
                    if res:
                        break

            stat[cur_stat] = res
            return res

        return dfs(0, maxChoosableInteger, desiredTotal)