README.md

464. 我能赢吗

English Version

题目描述

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

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

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

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

 

示例 1：

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

示例 2:

输入：maxChoosableInteger = 10, desiredTotal = 0
输出：true

示例 3:

输入：maxChoosableInteger = 10, desiredTotal = 1
输出：true

 

提示:

• 1 <= maxChoosableInteger <= 20
• 0 <= desiredTotal <= 300

解法

方法一：状态压缩 + 记忆化搜索

Python3

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        @cache
        def dfs(state, t):
            for i in range(1, maxChoosableInteger + 1):
                if (state >> i) & 1:
                    continue
                if t + i >= desiredTotal or not dfs(state | 1 << i, t + i):
                    return True
            return False

        s = (1 + maxChoosableInteger) * maxChoosableInteger // 2
        if s < desiredTotal:
            return False
        return dfs(0, 0)

Java

class Solution {
    private Map<Integer, Boolean> memo = new HashMap<>();

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int s = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
        if (s < desiredTotal) {
            return false;
        }
        return dfs(0, 0, maxChoosableInteger, desiredTotal);
    }

    private boolean dfs(int state, int t, int maxChoosableInteger, int desiredTotal) {
        if (memo.containsKey(state)) {
            return memo.get(state);
        }
        boolean res = false;
        for (int i = 1; i <= maxChoosableInteger; ++i) {
            if (((state >> i) & 1) == 0) {
                if (t + i >= desiredTotal
                    || !dfs(state | 1 << i, t + i, maxChoosableInteger, desiredTotal)) {
                    res = true;
                    break;
                }
            }
        }
        memo.put(state, res);
        return res;
    }
}

C++

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int s = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
        if (s < desiredTotal) return false;
        unordered_map<int, bool> memo;
        return dfs(0, 0, maxChoosableInteger, desiredTotal, memo);
    }

    bool dfs(int state, int t, int maxChoosableInteger, int desiredTotal, unordered_map<int, bool>& memo) {
        if (memo.count(state)) return memo[state];
        bool res = false;
        for (int i = 1; i <= maxChoosableInteger; ++i) {
            if ((state >> i) & 1) continue;
            if (t + i >= desiredTotal || !dfs(state | 1 << i, t + i, maxChoosableInteger, desiredTotal, memo)) {
                res = true;
                break;
            }
        }
        memo[state] = res;
        return res;
    }
};

Go

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	s := (1 + maxChoosableInteger) * maxChoosableInteger / 2
	if s < desiredTotal {
		return false
	}
	memo := map[int]bool{}
	var dfs func(int, int) bool
	dfs = func(state, t int) bool {
		if v, ok := memo[state]; ok {
			return v
		}
		res := false
		for i := 1; i <= maxChoosableInteger; i++ {
			if (state>>i)&1 == 1 {
				continue
			}
			if t+i >= desiredTotal || !dfs(state|1<<i, t+i) {
				res = true
				break
			}
		}
		memo[state] = res
		return res
	}
	return dfs(0, 0)
}

...