Leetcode 464. 我能赢吗 (状态压缩,记忆话搜索)

25
五月
2021


1到n的数,每个数在整个博弈过程中只能选一次。用f(i)表示在状态i下当前玩家是否必胜或者必败,状态i就是1到n个数选择情况,用一个二进制数表示

由状态i,可以计算当前分数,于是可以写出如下Python代码:

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal < maxChoosableInteger :
            return True
        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal:
            return False
        
        @lru_cache(None)
        def dfs(mask):
            cursum = 0
            for i in range(maxChoosableInteger):
                if mask >> i & 1 > 0:
                    cursum += (i + 1)
            
            for i in range(maxChoosableInteger):
                cur = 1 << i
                if cur & mask == 0:
                    if cursum + i + 1 >= desiredTotal or not dfs(mask | cur):
                        return True
            return False
        
        return dfs(0)

这段代码的缺点是,每次都要遍历一次多计算一次得分,因此我们可以用额外变量,把当前得分记录下来:

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal < maxChoosableInteger :
            return True
        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal:
            return False
        
        @lru_cache(None)
        def dfs(mask, cursum):
            for i in range(maxChoosableInteger):
                cur = 1 << i
                if cur & mask == 0:
                    if cursum + i + 1 >= desiredTotal or not dfs(mask | cur, cursum + i + 1):
                        return True
            return False
        
        return dfs(0, 0)

最后是C++代码实现:

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if(desiredTotal <= maxChoosableInteger){
            return true;
        }
        if(maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) {
            return false;
        }
        n = maxChoosableInteger;
        total = desiredTotal;
        f.resize(1 << n, -1);
        return helper(0, 0);
    }

    bool helper(int mask, int curSum) {
        if (f[mask] != -1){
            return f[mask];
        }
        for(int i = 0; i < n; i++) {
            int cur = (1 << i);
            if ((mask & cur) == 0) {
                if (curSum + i + 1 >= total || !helper(mask | cur, curSum + i + 1)){
                    f[mask] = 1;
                    return true;
                }
            }
        }
        f[mask] = 0;
        return false;
    }

    int n;
    int total;
    vector<int> f;
};

 

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员