题目描述：

LeetCode 464. Can I Win

In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:
maxChoosableInteger = 10
desiredTotal = 11

Output:
false

Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

题目大意：

在“100游戏”中，两个玩家轮流从整数1-10中取数相加，得到一个累加值。第一个使累加值达到或者超过100的玩家获胜。

我们修改游戏规则，用过的数字不能重复使用，会怎样呢？

例如，两个玩家可以轮流从1..15中无放回的取数字，使得累加值>=100。

给定整数 maxChoosableInteger 和 desiredTotal，判断第一个玩家是否一定能赢，假设两名玩家都采用最优策略。

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

解题思路：

记忆化搜索 + 位运算

由于maxChoosableInteger不大于20，因此可以通过整数state表示当前已经选择了哪些数字

state的第i位为1时，表示选择了数字i + 1

利用字典dp记录已经搜索过的状态

Python代码：

class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        dp = dict()
        def search(state, total):
            for x in range(maxChoosableInteger, 0, -1):
                if not state & (1 << (x - 1)):
                    if total + x >= desiredTotal:
                        dp[state] = True
                        return True
                    break
            for x in range(1, maxChoosableInteger + 1):
                if not state & (1 << (x - 1)):
                    nstate = state | (1 << (x - 1))
                    if nstate not in dp:
                        dp[nstate] = search(nstate, total + x)
                    if not dp[nstate]:
                        dp[state] = True
                        return True
            dp[state] = False
            return False
        if maxChoosableInteger >= desiredTotal: return True
        if (1 + maxChoosableInteger) * maxChoosableInteger < 2 * desiredTotal: return False
        return search(0, 0)

 

本文链接：http://bookshadow.com/weblog/2016/11/20/leetcode-can-i-win/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码