azl397985856 commented 2 years ago

464. 我能赢么

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/can-i-win/

前置知识

暂无

题目描述

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

yetfan commented 2 years ago

思路边界1：随便选一个就赢边界2：都选完了也赢不了

对于一个数i，选完了就能赢，返回true 对于一个数i，选完了之后，对手再选最优也不能赢，返回true

位运算表示二进制位置cur=1<<i，mask&cur==0表示未被访问过

@cache使用缓存减少递归运算次数

代码

class Solution:
    def canIWin(self, m: int, d: int) -> bool:
        if  d <= m:
            return True
        if (1 + m) * m / 2 < d:
            return False

        @cache
        def dfs(mask, cursum):
            for i in range(1,m+1):
                cur = 1 << i
                if cur & mask == 0:
                    if cursum+i >= d or not dfs(cur | mask, cursum+i):
                        return True
            return False
        dfs.cache_clear()
        return dfs(0, 0)

复杂度 时间 O(d*2^n) 空间 O(n)

ZacheryCao commented 2 years ago

Idea

DP

Code

class Solution:
    def canIWin(self, maxChoosableInteger, desiredTotal):
        seen = {}

        def can_win(choices, remainder):
            if choices[-1] >= remainder:
                return True
            seen_key = tuple(choices)
            if seen_key in seen:
                return seen[seen_key]
            for index in range(len(choices)):
                if not can_win(choices[:index] + choices[index + 1:], remainder - choices[index]):
                    seen[seen_key] = True
                    return True
            seen[seen_key] = False
            return False

        summed_choices = (maxChoosableInteger + 1) * maxChoosableInteger / 2
        if summed_choices < desiredTotal:
            return False
        choices = list(range(1, maxChoosableInteger + 1))
        return can_win(choices, desiredTotal)

Complexity

Time: (desiredTotal * 2^(maxChoosableInteger))

Space: (maxChoosableInteger^2)

zhy3213 commented 2 years ago

思路

破防了做几遍几遍不会不放代码了

li65943930 commented 2 years ago

public class Solution { public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

    if (maxChoosableInteger >= desiredTotal) return true;
    if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;

    Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 1];
    return dfs(maxChoosableInteger, desiredTotal, 0, dp);
}

private boolean dfs(int maxChoosableInteger, int desiredTotal, int state, Boolean[] dp) {
    if (dp[state] != null)
        return dp[state];
    for (int i = 1; i <= maxChoosableInteger; i++){
        int tmp = (1 << (i - 1));
        if ((tmp & state) == 0){
            if (desiredTotal - i <= 0 || !dfs(maxChoosableInteger, desiredTotal - i, tmp|state, dp)) {
                dp[state] = true;
                return true;
            }
        }
    }
    dp[state] = false;
    return false;
}

}

yan0327 commented 2 years ago

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
    if maxChoosableInteger >= desiredTotal{
        return true
    }
    if maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal{
        return false
    }
    have := make([]bool, 1 << maxChoosableInteger)
    var dp func(picked,account int) bool
    dp = func(picked,account int) bool{
        if have[picked]{
            return true
        }
        for i:=1;i<maxChoosableInteger+1;i++{
            cur := 1 << (i-1)
            if picked&cur != 0{
                continue
            }
            if i >= account || !dp(picked|cur,account-i){
                have[picked] = true
                return true
            }
        }
        have[picked] = false
        return false
    }
    return dp(0,desiredTotal)
}

Aobasyp commented 2 years ago

思路动态规划+状态压缩

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

bool dfs(int n,int s,int t,int S,unordered_map<int,int>& d){
    if(d[S]) return  d[S];
    int& ans = d[S];

    if(s >= t){
        return ans = true;
    }
    if(S == (((1 << n)-1) << 1)){
        return ans = false;
    }

    for(int m = 1;m <=n;++m){
        if(S & (1 << m)){
            continue;
        }
        int nextS = S|(1 << m);
        if(s+m >= t){
            return ans = true;
        }
        bool r1 = dfs(n,s+m,t,nextS,d);
        if(!r1){
            return ans = true;
        }
    }
    return ans = false;
}

};

1149004121 commented 2 years ago

我能赢吗

思路

动态规划。如果不进行记忆化，则时间复杂度为N！，会超时。

代码

function canIWin(maxChoosableInteger: number, desiredTotal: number): boolean {
    if(maxChoosableInteger > desiredTotal) return true;
    let sum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
    if(sum < desiredTotal) return false;
    let visited = {};
    return dfs(0, 0);

    function dfs(choosed: number, total: number): boolean{
        if(visited[choosed] !== undefined){
            return visited[choosed];
        }
        if(total >= desiredTotal){
            visited[choosed] = false;
            return false;
        }
        for(let i = 0; i < maxChoosableInteger; i++){
            if((choosed & (1 << i)) === 0){
                if(!dfs(choosed | (1 << i), total + i + 1)){
                    visited[choosed] = true;
                    return true;
                }
            }
        };
        return (visited[choosed] = false);
    }
};

复杂度分析

时间复杂度：O(2^ n )。
空间复杂度：O(2^ n )。

Liuxy94 commented 2 years ago

思路

参考题解状压DP

代码

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal:
            return False
        # picked 用于保存当前已经选择过的数。
        # acc 表示当前累计的数字和
        def backtrack(picked, acc):
            if acc >= desiredTotal:
                return False
            if len(picked) == maxChoosableInteger:
                # 说明全部都被选了，没得选了，返回 False， 代表输了。
                return False
            for n in range(1, maxChoosableInteger + 1):
                if n not in picked:
                    picked.add(n)
                    # 对方有一种情况赢不了，我就选这个数字就能赢了，返回 true，代表可以赢。
                    if not backtrack(picked, acc + n):
                        picked.remove(n)
                        return True
                    picked.remove(n)
            return False

        # 初始化集合，用于保存当前已经选择过的数。
        return backtrack(set(), 0)

复杂度分析

时间： O(d2^n)

空间： O(n)

haixiaolu commented 2 years ago

题解都看不明白，先抄个答案吧

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal:
            return False
        # picked 用于保存当前已经选择过的数。
        # acc 表示当前累计的数字和
        def backtrack(picked, acc):
            if acc >= desiredTotal:
                return False
            if len(picked) == maxChoosableInteger:
                # 说明全部都被选了，没得选了，返回 False， 代表输了。
                return False
            for n in range(1, maxChoosableInteger + 1):
                if n not in picked:
                    picked.add(n)
                    # 对方有一种情况赢不了，我就选这个数字就能赢了，返回 true，代表可以赢。
                    if not backtrack(picked, acc + n):
                        picked.remove(n)
                        return True
                    picked.remove(n)
            return False

        # 初始化集合，用于保存当前已经选择过的数。
        return backtrack(set(), 0)

zhangzz2015 commented 2 years ago

思路

考虑Top down方法，因为每个num只能选择1次，当我在当前状态下，有一些num被选择了，剩下的desiredTotal，我可以选择剩下的num，如果我选择了某一个num后，另外一个player的情况返回false，则表明，我能赢，返回true。如果我尝试所有剩下的num，都不能赢，则返回false。递归函数为，当我面临desiredTotal以及剩下num，我能赢还是输，赢则为true，输则为false。进一步考虑加上mem，mem状态不能用desiredTotal，必须要用visit flag的状态，可把visit 转成string，或者利用bit 位压缩。例如总共有 4位 [0 1 0 1] ，选择了两位，则可把这个转化为bit，同步维护index。

关键点

代码

语言支持：C++

C++ Code:


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

    }

    // play =true   first play. 
    // play =false    second play
    bool   dfs(int maxChoosableInteger, int desiredTotal,  vector<bool>& visit, int& index, unordered_map<int, bool> & memo)
    {
        if(desiredTotal<=0) // when current player met desiredTotal <=0. It mean you loose. 
            return false;

        bool ret = false; 
        if (memo.count(index)) {
            return memo[index];
        }        
        for(int i=1; i<=maxChoosableInteger; i++)
        {
            if(visit[i]) continue; 
            visit[i] = true; 
            index +=(1<<(i));
            if(dfs(maxChoosableInteger, desiredTotal-i, visit, index,  memo)==false)
            {
                visit[i] = false;
                index -=(1<<(i));
                ret = true; 
                break; 
            }
            index -=(1<<(i));            
            visit[i] = false; 
        } 
        memo[index] = ret; 
        return ret; 
    }
};

ZJP1483469269 commented 2 years ago

class Solution:
    def canIWin(self, n: int, tar: int) -> bool:
        if n * (n + 1) // 2 < tar:
            return False
        dp = [None] * (1 << (n + 1))
        def dfs(state , tar):
            if dp[state] != None:
                return dp[state]
            for i in range(1,n + 1):
                if (state >> i) & 1:
                    continue
                cur = state | (1 << i)
                if i >= tar or not dfs(cur , tar - i):
                    dp[state] = True
                    return True
            dp[state] = False
            return False

        return dfs(0,tar)

junbuer commented 2 years ago

思路

动态规划 + dfs

代码

class Solution:
def canIWin(self, maxChoosableInteger, desiredTotal):
    if maxChoosableInteger >= desiredTotal: return True
    if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal: return False
    def dfs(state, desiredTotal, dp):
        if dp[state] != None:
            return dp[state]
        for i in range(1, maxChoosableInteger + 1):
            cur = 1 << (i - 1)
            if cur & state != 0:
                continue

            if i >= desiredTotal or not dfs(cur | state, desiredTotal - i, dp):
                dp[state] = True
                return True
        dp[state] = False
        return False

    return dfs(0, desiredTotal, [None] * (1 << maxChoosableInteger))

复杂度分析

时间复杂度：$O(2^n)$
空间复杂度：$O(2^n)$

tongxw commented 2 years ago

思路

回溯。因为需要记忆化递归，visited数组需要序列化才能用做key。但是考虑到数字<20，可以用一个32位整型标记数字是否已经选择。

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger > desiredTotal) {
            return true;
        }
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) {
            return false;
        }

        Map<Integer, Boolean> memo = new HashMap<>();
        return dfs(maxChoosableInteger, desiredTotal, 0, memo);
    }

    private boolean dfs(int n, int target, int picked, Map<Integer, Boolean> memo) {
        if (memo.containsKey(picked)) {
            return memo.get(picked);
        }

        for (int i=1; i<=n; i++) {
            int mask = 1 << (i -1);
            if ((picked & mask) != 0) {
                continue;
            }

            if (i >= target || !dfs(n, target - i, picked | mask, memo)) {
                // i win or you lose
                memo.put(picked, true);
                return true;
            }
        }

        memo.put(picked, false);
        return false;
    }
}

TC: O(2^N) SC: O(2^N)

Tesla-1i commented 2 years ago

class Solution:
    def canIWin(self, maxChoosableInteger, desiredTotal):
        seen = {}

        def can_win(choices, remainder):
            if choices[-1] >= remainder:
                return True
            seen_key = tuple(choices)
            if seen_key in seen:
                return seen[seen_key]
            for index in range(len(choices)):
                if not can_win(choices[:index] + choices[index + 1:], remainder - choices[index]):
                    seen[seen_key] = True
                    return True
            seen[seen_key] = False
            return False

        summed_choices = (maxChoosableInteger + 1) * maxChoosableInteger / 2
        if summed_choices < desiredTotal:
            return False
        choices = list(range(1, maxChoosableInteger + 1))
        return can_win(choices, desiredTotal)

LannyX commented 2 years ago

思路

状态压缩 + 回溯

代码

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if(maxChoosableInteger >= desiredTotal){
            return true;
        }
        if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal){
            return false;
        }
        Boolean[] dp = new Boolean[(1 << maxChoosableInteger)];

        return canWin(maxChoosableInteger, desiredTotal, 0, dp);
    }
    boolean canWin(int max, int total, int state, Boolean[] dp){
        if(dp[state] != null){
            return dp[state];
        }
        for(int i = 1; i <= max; i++){
            int cur = (1 << (i - 1));
            if((cur & state) == 0){
                if(total - i <= 0 || !canWin(max, total - i, cur|state, dp)){
                    dp[state] = true;
                    return true;
                }
            }
        }
        dp[state] = false;
        return false;
    }
}

复杂度分析

时间复杂度：O(2^n)

ACcentuaLtor commented 2 years ago

状态压缩，没看懂，学习一下这个答案： class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:

    #注意这种情况对应数字拿完都达不到目标，此时双方都不会获胜，现在有个这样的case，需要特判
    if desiredTotal>maxChoosableInteger*(maxChoosableInteger+1)//2: 
        return False
    table = {} 
    def dfs(cur,used):
        #每个used对应的cur是唯一的，传2个参数只是避免解析used花费大量时间，因此used在table中就可以直接返回结果
        #如果不带记忆，复杂度达到20！级别，必定超时
        if used in table: #注意每个used对应的cur是唯一的，传2个参数只是避免解析used花费大量时间
            return table[used]
        for j in range(1,maxChoosableInteger+1): #遍历每种操作
            if used|(1<<(j-1))==used: # 这说明j已经被用过了，不能再用
                continue
            if cur+j>=desiredTotal: # 满足边界条件，判断为必胜
                table[used]=True
                return True
            if not dfs(cur+j,used|(1<<(j-1))): # 只要找到一个能让对方必败的选择，这个状态就是必胜
                table[used]=True
                return True
        table[used]=False # 循环完所有选择还是没找到能让对方必败的选择，说明当前这个状态必败
        return False

    return dfs(0,0)

shamworld commented 2 years ago

var canIWin = function (maxChoosableInteger, desiredTotal) {
  // 直接获胜
  if (maxChoosableInteger >= desiredTotal) return true;

  // 全部拿完也无法到达
  var sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2;
  if (desiredTotal > sum) return false;

  // 记忆化
  var dp = {};

  /**
   * @param {number} total 剩余的数量
   * @param {number} state 使用二进制位表示抽过的状态
   */
  function f(total, state) {
    // 有缓存
    if (dp[state] !== undefined) return dp[state];

    for (var i = 1; i <= maxChoosableInteger; i++) {
      var curr = 1 << i;
      // 已经抽过这个数
      if (curr & state) continue;
      // 直接获胜
      if (i >= total) return (dp[state] = true);
      // 可以让对方输
      if (!f(total - i, state | curr)) return (dp[state] = true);
    }

    // 没有任何让对方输的方法
    return (dp[state] = false);
  }

  return f(desiredTotal, 0);
};

zol013 commented 2 years ago

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if sum(range(maxChoosableInteger+1)) < desiredTotal:
            return False

        @lru_cache(None)
        def dp(picked, acc):
            if acc >= desiredTotal:
                return False
            if picked == (1 << (maxChoosableInteger + 1)) - 1:
                return False
            for n in range(1, maxChoosableInteger + 1):
                if picked & 1 << n == 0:
                    if not dp(picked | 1 << n, acc + n):
                        return True
            return False
        return dp(0, 0)

JudyZhou95 commented 2 years ago

代码

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal < maxChoosableInteger:
            return True

        if sum(range(maxChoosableInteger+1)) < desiredTotal:
            return False

        self.memo = {}
        return self.helper(list(range(1, maxChoosableInteger+1)), desiredTotal)

    def helper(self, nums, desiredTotal):
        hash = str(nums)
        if hash in self.memo:
            return self.memo[hash]

        if nums[-1] >= desiredTotal:
            return True

        for i in range(len(nums)):
            if not self.helper(nums[:i] + nums[i+1:], desiredTotal-nums[i]):
                self.memo[hash] = True
                return True

        self.memo[hash] = False
        return False

复杂度

TC: O(2^N) SC: O(2^N)

falconruo commented 2 years ago

思路: bitmask + hashmap

复杂度分析:

时间复杂度: O(N*2^N)，N为maxChoosableInteger
空间复杂度: O(2^N), hashmap空间

代码(C++):

方法一、哈希表hashmap记录状态
class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;

        int sum = maxChoosableInteger * (maxChoosableInteger - 1) /2;
        if (sum < desiredTotal) return false;
        unordered_map<int, bool> mp(maxChoosableInteger + 1);
        return dfs(0, maxChoosableInteger, desiredTotal, mp);
    }
private:
    bool dfs(int mask, int maxN, int desiredT, unordered_map<int, bool>& mp) {
        if (mp.count(mask)) return mp[mask];
        for (int i = 1; i <= maxN; i++) {
            int state = 1 << (i - 1);
            if ((mask & state) == 0) { // i is not picked
                if (desiredT - i <= 0 || !dfs(mask | state, maxN, desiredT - i, mp)) {
                    mp[mask] = true;
                    return true;
                }
            }
        }
        mp[mask] = false;
        return false;
    }
};

GaoMinghao commented 2 years ago

思路

这题目真的只是middle嘛，感觉每个点都在我的认知外😢

代码

public class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

        if (maxChoosableInteger >= desiredTotal) return true;
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;

        Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 1];
        return dfs(maxChoosableInteger, desiredTotal, 0, dp);
    }

    private boolean dfs(int maxChoosableInteger, int desiredTotal, int state, Boolean[] dp) {
        if (dp[state] != null)
            return dp[state];
        for (int i = 1; i <= maxChoosableInteger; i++){
            int tmp = (1 << (i - 1));
            if ((tmp & state) == 0){
                if (desiredTotal - i <= 0 || !dfs(maxChoosableInteger, desiredTotal - i, tmp|state, dp)) {
                    dp[state] = true;
                    return true;
                }
            }
        }
        dp[state] = false;
        return false;
    }
}

xianxianxianyu commented 2 years ago

大佬的

class Solution {
private:
    bool** d;
    // 递归函数, 返回当前状态下先手是否能赢，赢返回true
    // state: 最大为1<<maxChoosableInteger - 1
    // maxChoosableInteger: 固定不变
    // desiredTotal: 这个按照每一轮取值会变化
    bool dfs(int state, int maxChoosableInteger, int desiredTotal)
    {
        // cout << state << " " << d[state] << endl;
        if (d[state] != nullptr)
        {
            return *d[state];
        }

        // 这里会从尝试各种可能性
        for (int i = 1; i <= maxChoosableInteger; ++i)
        {

            // 需要排除state里已经选择可能性
            if (state & (1 << (i-1)))
            {
                continue;
            }
            // cout << "try " <<  state << " " << i << " " << (state & (1 << (i-1))) << endl;
            // 只取成功的情况，则直接返回成功
            if (i >= desiredTotal || !dfs((state | (1<<(i-1))), maxChoosableInteger, desiredTotal-i))
            {
                d[state] = new bool(true);
                return true;
            }
        }

        // 如果没成功情况，那么肯定失败了
        d[state] = new bool(false);
        return false;
    }
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal)
        {
            return true;
        }
        if ((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal)
        {
            return false;
        }

        d = new bool*[1<<maxChoosableInteger];
        memset(d, 0, sizeof(bool*) * (1<<maxChoosableInteger));

        return dfs(0, maxChoosableInteger, desiredTotal);
    }

};

Richard-LYF commented 2 years ago

class Solution: def canIWin(self, maxChoosableInteger, desiredTotal): seen = {}

    def can_win(choices, remainder):
        if choices[-1] >= remainder:
            return True
        seen_key = tuple(choices)
        if seen_key in seen:
            return seen[seen_key]
        for index in range(len(choices)):
            if not can_win(choices[:index] + choices[index + 1:], remainder - choices[index]):
                seen[seen_key] = True
                return True
        seen[seen_key] = False
        return False

    summed_choices = (maxChoosableInteger + 1) * maxChoosableInteger / 2
    if summed_choices < desiredTotal:
        return False
    choices = list(range(1, maxChoosableInteger + 1))
    return can_win(choices, desiredTotal)

hdyhdy commented 2 years ago

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
    if maxChoosableInteger*(1+maxChoosableInteger)/2 < desiredTotal {
        return false
    }
    // dp表示每种选择下会赢或输
    dp := make([]bool, 1<<maxChoosableInteger)
    return helper(maxChoosableInteger, desiredTotal, dp, 0)

}

// state是当前选中状态的十进制表示
func helper(maxChoosableInteger int, desiredTotal int, dp []bool, state int) bool {
    if dp[state] != false {
        return dp[state]
    }
    for i := 1; i <= maxChoosableInteger; i++ {
        cur := 1 << (i - 1)
        // 如果当前所选的数字已经被选了，则跳过
        if cur&state != 0 {
            continue
        }
        // 所需要的数小于可选数(这次我就能赢) || 递归本函数为假(下一个人要输的话我肯定赢)，state|cur 表示选中当前数
        if desiredTotal-i <= 0 || !helper(maxChoosableInteger, desiredTotal-i, dp, state|cur) {
            dp[state] = true
            return true
        }
    }
    dp[state] = false
    return false
}

Moin-Jer commented 2 years ago

class Solution { public boolean canIWin(int maxChoosableInteger, int desiredTotal) { if(maxChoosableInteger >= desiredTotal) return true; if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;

    return dfs(0, desiredTotal, new Boolean[1 << maxChoosableInteger], maxChoosableInteger);
}

private boolean dfs(int state, int desiredTotal, Boolean[] dp, int maxChoosableInteger){
    if(dp[state] != null){
        return dp[state];
    }

    for(int i = 1; i <= maxChoosableInteger; i++){
        int cur = 1 << (i - 1);
        if((cur & state) != 0){
            continue;
        }

        if(i >= desiredTotal || !dfs(cur|state, desiredTotal - i, dp, maxChoosableInteger)){
            return dp[state] = true;
        }
    }
    return dp[state] = false;
}

}

biaohuazhou commented 2 years ago

public class Solution { public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

    if (maxChoosableInteger >= desiredTotal) return true;
    if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;

    Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 1];
    return dfs(maxChoosableInteger, desiredTotal, 0, dp);
}

private boolean dfs(int maxChoosableInteger, int desiredTotal, int state, Boolean[] dp) {
    if (dp[state] != null)
        return dp[state];
    for (int i = 1; i <= maxChoosableInteger; i++){
        int tmp = (1 << (i - 1));
        if ((tmp & state) == 0){
            if (desiredTotal - i <= 0 || !dfs(maxChoosableInteger, desiredTotal - i, tmp|state, dp)) {
                dp[state] = true;
                return true;
            }
        }
    }
    dp[state] = false;
    return false;
}

}

Toms-BigData commented 2 years ago

不懂，先打卡

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
    if maxChoosableInteger*(1+maxChoosableInteger)/2 < desiredTotal {
        return false
    }
    // dp表示每种选择下会赢或输
    dp := make([]bool, 1<<maxChoosableInteger)
    return helper(maxChoosableInteger, desiredTotal, dp, 0)

}

// state是当前选中状态的十进制表示
func helper(maxChoosableInteger int, desiredTotal int, dp []bool, state int) bool {
    if dp[state] != false {
        return dp[state]
    }
    for i := 1; i <= maxChoosableInteger; i++ {
        cur := 1 << (i - 1)
        // 如果当前所选的数字已经被选了，则跳过
        if cur&state != 0 {
            continue
        }
        // 所需要的数小于可选数(这次我就能赢) || 递归本函数为假(下一个人要输的话我肯定赢)，state|cur 表示选中当前数
        if desiredTotal-i <= 0 || !helper(maxChoosableInteger, desiredTotal-i, dp, state|cur) {
            dp[state] = true
            return true
        }
    }
    dp[state] = false
    return false
}

hx-code commented 2 years ago

var canIWin = function (maxChoosableInteger, desiredTotal) { // 直接获胜 if (maxChoosableInteger >= desiredTotal) return true;

// 全部拿完也无法到达 var sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2; if (desiredTotal > sum) return false;

// 记忆化 var dp = {};

/**

@param {number} total 剩余的数量
@param {number} state 使用二进制位表示抽过的状态 */ function f(total, state) { // 有缓存 if (dp[state] !== undefined) return dp[state];

for (var i = 1; i <= maxChoosableInteger; i++) { var curr = 1 << i; // 已经抽过这个数 if (curr & state) continue; // 直接获胜 if (i >= total) return (dp[state] = true); // 可以让对方输 if (!f(total - i, state | curr)) return (dp[state] = true); }

// 没有任何让对方输的方法 return (dp[state] = false); }

return f(desiredTotal, 0); };

stackvoid commented 2 years ago

思路

看题解，带备忘录的递归

代码

public class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false; //1,..maxChoosable数列总和都比目标和小
        int[] state = new int[maxChoosableInteger + 1];  //state[1]=1表示1被选了

        return backtraceWitMemo(state, desiredTotal, new HashMap<String, Boolean>());
    }

    private boolean backtraceWitMemo(int[] state, int desiredTotal, HashMap<String, Boolean> map) {
        String key = Arrays.toString(state); //这里比较关键，如何表示这个唯一的状态，例如[2,3]和[3,2]都是"0011"，状态一样
        if (map.containsKey(key)) return map.get(key);  //如果已经记忆了这样下去的输赢结果,记忆是为了防止如[2,3]，[3,2]之后的[1,4,5,..]这个选择区间被重复计算

        for (int i = 1; i < state.length; i++){
            if (state[i] == 0){ //如果这个数字i还没有被选中
                state[i] = 1;
                //如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了
                if (desiredTotal - i <= 0 || !backtraceWitMemo(state, desiredTotal - i, map)) {
                    map.put(key, true);
                    state[i] = 0; //在返回之前回溯
                    return true;
                }
                //如果不能赢也要记得回溯
                state[i] = 0;
            }
        }
        //如果都赢不了
        map.put(key, false);
        return false;
    }
}

复杂度分析

Time O(N) Space O(N)

guangsizhongbin commented 2 years ago

class Solution { public boolean canIWin(int maxChoosableInteger, int desiredTotal) { // 1. 可选择的数之后小于desiredToal，两者都不能赢 // (首项 + 尾项 ) x 项数 / 2 if( (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal){ return false; }

    int[] state = new int[maxChoosableInteger + 1];

    // 用HashMap记忆化，记录已经出现来的state
    return canWin(state, desiredTotal, new HashMap<String, Boolean>());
}

public boolean canWin(int[] state, int total, Map<String, Boolean> hmap){
    // 如果已经有这项了，直接返回
    String key = Arrays.toString(state);
    if (hmap.containsKey(key)){
        return hmap.get(key);
    }

    // 处理子问题
    for (int i = 1; i < state.length; i++){
        // 未取
        if (state[i] == 0){
            state [i] = 1;
            if(total - i <= 0 || !canWin(state, total - i, hmap)){
                hmap.put(key, true);
                state[i] = 0;
                return true;
            }
            state[i] = 0;
        }
    }
    hmap.put(key, false);
    return false;
}

}

alongchong commented 2 years ago

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if(maxChoosableInteger >= desiredTotal) return true;
        if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;

        return dfs(0, desiredTotal, new Boolean[1 << maxChoosableInteger], maxChoosableInteger);
    }

    private boolean dfs(int state, int desiredTotal, Boolean[] dp, int maxChoosableInteger){
        if(dp[state] != null){
            return dp[state];
        }

        for(int i = 1; i <= maxChoosableInteger; i++){
            int cur = 1 << (i - 1);
            if((cur & state) != 0){
                continue;
            }

            if(i >= desiredTotal || !dfs(cur|state, desiredTotal - i, dp, maxChoosableInteger)){
                return dp[state] = true;
            }
        }
        return dp[state] = false;
    }
}

xuhzyy commented 2 years ago

看题解

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal:
            return False

        @lru_cache(None)
        def dp(picked, acc):
            if acc >= desiredTotal:
                return False
            if picked == (1 << (maxChoosableInteger + 1)) - 1:
                return False
            for n in range(1, maxChoosableInteger + 1):
                if picked & 1 << n == 0:
                    if not dp(picked | 1 << n, acc + n):
                        return True
            return False

        return dp(0, 0)

CodingProgrammer commented 2 years ago

思路

回溯

代码

class Solution {
    int N;
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal) return false; 
        this.N = maxChoosableInteger;
        char[] state = new char[this.N + 1]; // 记录每个数是否使用，state[i] = '1' 为 i 已经使用
        Arrays.fill(state, '0');
        Map<String, Boolean> memo = new HashMap<>();
        return backtracking(state, desiredTotal, memo);
    }

    private boolean backtracking(char[] state, int target, Map<String, Boolean> memo) {
        String key = new String(state); // 记录当前数字使用状态， [2,3] 和 [3,2] 为同一状态
        if (memo.containsKey(key)) return memo.get(key);

        for (int i = 1; i <= this.N; i++) {
            // 当前数字未使用
            if (state[i] == '0') {
                state[i] = '1';
                // 如果当前凑出了 target 或者对方未凑出 target，则胜利
                if (target - i <= 0 || !backtracking(state, target - i, memo)) {
                    memo.put(key, true);
                    state[i] = '0'; // 回溯状态
                    return true;
                }
                state[i] = '0'; // 回溯状态
            }
        }
        memo.put(key, false);
        return false;
    }
}

复杂度

Time:O(2^N)
Space: O(M*N)

pwqgithub-cqu commented 2 years ago

思路：动态规划+dfs 代码：class Solution: def canIWin(self, maxChoosableInteger, desiredTotal): if maxChoosableInteger >= desiredTotal: return True if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal: return False def dfs(state, desiredTotal, dp): if dp[state] != None: return dp[state] for i in range(1, maxChoosableInteger + 1): cur = 1 << (i - 1) if cur & state != 0: continue

            if i >= desiredTotal or not dfs(cur | state, desiredTotal - i, dp):
                dp[state] = True
                return True
        dp[state] = False
        return False

    return dfs(0, desiredTotal, [None] * (1 << maxChoosableInteger))

复杂度：时间复杂度：O(2^n) 空间复杂度：O(2^n)

callmeerika commented 2 years ago

思路

状压DP

代码

var dfs = function(maxChoosableInteger, desiredTotal, state, dp) {
    if (dp[state] !== undefined) return dp[state];
    for (let i = 1; i <= maxChoosableInteger; i++){
        let tmp = 1 << (i - 1);
        if ((tmp & state) === 0){
            if (i >= desiredTotal || !dfs(maxChoosableInteger, desiredTotal - i, tmp | state, dp)) {
                dp[state] = true;
                return true;
            }
        }
    }
    dp[state] = false;
    return false;
}
var canIWin = function(maxChoosableInteger, desiredTotal) {
    if (maxChoosableInteger >= desiredTotal) return true;
    if (desiredTotal > (maxChoosableInteger + 1) * maxChoosableInteger/2) return false;
    let dp = {};
    return dfs(maxChoosableInteger, desiredTotal, 0, dp);
};

复杂度

时间复杂度：O(2^n)
空间复杂度：O(2^n)

Hacker90 commented 2 years ago

class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool: if desiredTotal <= maxChoosableInteger: return True if sum(range(maxChoosableInteger + 1)) < desiredTotal: return False

picked 用于保存当前已经选择过的数。

    # acc 表示当前累计的数字和
    def backtrack(picked, acc):
        if acc >= desiredTotal:
            return False
        if len(picked) == maxChoosableInteger:
            # 说明全部都被选了，没得选了，返回 False， 代表输了。
            return False
        for n in range(1, maxChoosableInteger + 1):
            if n not in picked:
                picked.add(n)
                # 对方有一种情况赢不了，我就选这个数字就能赢了，返回 true，代表可以赢。
                if not backtrack(picked, acc + n):
                    picked.remove(n)
                    return True
                picked.remove(n)
        return False

    # 初始化集合，用于保存当前已经选择过的数。
    return backtrack(set(), 0)

Jay214 commented 2 years ago

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function (maxChoosableInteger, desiredTotal) {
    // 直接获胜
    if (maxChoosableInteger >= desiredTotal) return true;

    // 全部拿完也无法到达
    var sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (desiredTotal > sum) return false;

    // 记忆化
    var dp = {};

    /**
     * @param {number} total 剩余的数量
     * @param {number} state 使用二进制位表示抽过的状态
     */
    function f(total, state) {
        // 有缓存
        if (dp[state] !== undefined) return dp[state];

        for (var i = 1; i <= maxChoosableInteger; i++) {
            var curr = 1 << i;
            // 已经抽过这个数
            if (curr & state) continue;
            // 直接获胜
            if (i >= total) return dp[state] = true;
            // 可以让对方输
            if (!f(total - i, state | curr)) return dp[state] = true;
        }

        // 没有任何让对方输的方法
        return dp[state] = false;
    }

    return f(desiredTotal, 0);
};

CoreJa commented 2 years ago

思路

旧题新做，虽然这次很快找到了思路，但是debug的路上出了一点差错，猜想正确但是没改过来。不然至少能用@cache给解了。基本算做出来了吧)。

这个题本质就是要去模拟，题目中所表达的"Assume both players play optimally."其实意思就是双方两个人都会把所有情况探个遍，换句话说就是我一个人会把我的所有可能和对方的所有可能全部探索一遍，以找到可能的解。所以模拟就直接DFS了。

DFS：用visited数组表示当前数是否被取用，DFS递归需要传递剩余的desiredTotal够不够减，设为target，遍历试探所有没有被访问的数，如果取的这个数直接大于target，说明这次试探成功，返回True，否则就递归调用到下一层，传入target-num。应当注意visited数组如果当作全局变量则需要像八皇后的题目，在递归调用结束后及时修改为未访问，或者作为递归参数每次copy后传入，否则会卡在用例40/57(10, 40)。复杂度$O(n!)$
DFS+记忆化+偷懒cache：上面的思路是正确的，只是回溯会进行多次重复计算，我们可以用@cache偷懒，让修饰器帮我们完成记忆化。复杂度$O(2^n)$
- 注意此时DFS必须把visited当作参数传入，因为@cache只能记忆入参和结果。
- visited如果仍然是数组则无法完成@cache的hash化(它是通过dict存入参的)，故可以用状态压缩的位集或者tuple来实现(后者内存爆炸，高达200MB)
DFS+记忆化(单一参数)：偷懒法的问题在于不得不使用target和visited两个参数来记忆。实际上，对于任意一个状态visited，它所对应的target一定是固定值。visited中，二进制下1的位数表示当前已经取走的num，所以对于任意visited，它有且仅有一个target对应，所以我们只使用visited来记忆化即可。构建一个数组dp，长度为$2^n$，初始化为None，每次确定答案时，存到dp数组，递归时先访问dp，有答案就不用继续dfs了。复杂度$O(2^n)$

代码

class Solution:
    # DFS： 用`visited`数组表示当前数是否被取用，DFS递归需要传递剩余的desiredTotal够不够减，设为`target`，遍历试探所有没
    # 有被访问的数，如果取的这个数直接大于`target`，说明这次试探成功，返回True，否则就递归调用到下一层，传入`target-num`。
    # 应当注意`visited`数组如果当作全局变量则需要像八皇后的题目，在递归调用结束后及时修改为未访问，或者作为递归参数每次copy后
    # 传入，否则会卡在用例40/57(10, 40)。复杂度$O(n!)$
    def canIWin1(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if (maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal:
            return False
        visited = [False] * (maxChoosableInteger + 1)

        def dfs(target):
            for num in range(1, maxChoosableInteger + 1):
                if visited[num]:
                    continue
                if num >= target:
                    return True
                visited[num] = True
                if not dfs(target - num):
                    visited[num] = False
                    return True
                visited[num] = False
            return False

        return dfs(desiredTotal)

    # DFS+记忆化+偷懒`cache`：上面的思路是正确的，只是回溯会进行多次重复计算，我们可以用`@cache`偷懒，让修饰器帮我们完成
    # 记忆化。复杂度$O(2^n)$
    # - 注意此时DFS必须把`visited`当作参数传入，因为@cache只能记忆入参和结果。
    # - `visited`如果仍然是数组则无法完成`@cache`的hash化(它是通过dict存入参的)，故可以用状态压缩的位集或者`tuple`来实现
    #   (后者内存爆炸，高达200MB)
    def canIWin2(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if (maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal:
            return False

        @cache
        def dfs(target, visited):
            for num in range(1, maxChoosableInteger + 1):
                cur = 1 << (num - 1)
                if visited & cur:
                    continue
                if num >= target or not dfs(target - num, visited | cur):
                    return True
            return False

        return dfs(desiredTotal, 0)

    # DFS+记忆化(单一参数)：偷懒法的问题在于不得不使用`target`和`visited`两个参数来记忆。实际上，对于任意一个状态
    # `visited`，它所对应的`target`一定是固定值。`visited`中，二进制下`1`的位数表示当前已经取走的num，所以对于任意
    # `visited`，它有且仅有一个`target`对应，所以我们只使用`visited`来记忆化即可。构建一个数组`dp`，长度为$2^n$，
    # 初始化为None，每次确定答案时，存到`dp`数组，递归时先访问`dp`，有答案就不用继续dfs了。复杂度$O(2^n)$
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if (maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal:
            return False
        dp = [None] * (1 << maxChoosableInteger)

        def dfs(target, visited):
            if dp[visited] is not None:
                return dp[visited]
            for num in range(1, maxChoosableInteger + 1):
                cur = 1 << (num - 1)
                if visited & cur:
                    continue
                if num >= target or not dfs(target - num, visited | cur):
                    dp[visited] = True
                    return True
            dp[visited] = False
            return False

        return dfs(desiredTotal, 0)

WANGDI-1291 commented 2 years ago

代码

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal:
            return False
        # picked 用于保存当前已经选择过的数。
        # acc 表示当前累计的数字和
        def backtrack(picked, acc):
            if acc >= desiredTotal:
                return False
            if len(picked) == maxChoosableInteger:
                # 说明全部都被选了，没得选了，返回 False， 代表输了。
                return False
            for n in range(1, maxChoosableInteger + 1):
                if n not in picked:
                    picked.add(n)
                    # 对方有一种情况赢不了，我就选这个数字就能赢了，返回 true，代表可以赢。
                    if not backtrack(picked, acc + n):
                        picked.remove(n)
                        return True
                    picked.remove(n)
            return False

        # 初始化集合，用于保存当前已经选择过的数。
        return backtrack(set(), 0)

HWFrankFung commented 2 years ago

Codes

var canIWin = function (maxChoosableInteger, desiredTotal) {
    if (maxChoosableInteger >= desiredTotal) {
        return true
    };
    let sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (desiredTotal > sum) {
        return false
    };
    let map = new Map();
    let visited = new Array(maxChoosableInteger + 1).fill(0);
    return dfs(maxChoosableInteger, desiredTotal, visited, map)
};
function dfs(maxChoosableInteger, desiredTotal, visited,map) {
    let state = visited.toString();
    if (map.has(state)) {
        return map.get(state)
    };
    for (let i = 1; i <= maxChoosableInteger; i++) {
        if (!visited[i]) {
            if (desiredTotal - i <= 0) {
                map.set(state, true);
                return true
            };
            visited[i] = 1;
            let result = dfs(maxChoosableInteger, desiredTotal - i, visited,map);
            visited[i] = 0;
            if (result == false) {
                map.set(state, true);
                return true;
            }
        }
    }
    map.set(state, false);
    return false;
}

honeymeng-hub commented 2 years ago

class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool: if desiredTotal <= maxChoosableInteger: return True if sum(range(maxChoosableInteger + 1)) < desiredTotal: return False

picked 用于保存当前已经选择过的数。

    # acc 表示当前累计的数字和
    def backtrack(picked, acc):
        if acc >= desiredTotal:
            return False
        if len(picked) == maxChoosableInteger:
            # 说明全部都被选了，没得选了，返回 False， 代表输了。
            return False
        for n in range(1, maxChoosableInteger + 1):
            if n not in picked:
                picked.add(n)
                # 对方有一种情况赢不了，我就选这个数字就能赢了，返回 true，代表可以赢。
                if not backtrack(picked, acc + n):
                    picked.remove(n)
                    return True
                picked.remove(n)
        return False

    # 初始化集合，用于保存当前已经选择过的数。
    return backtrack(set(), 0)

z1ggy-o commented 2 years ago

思路

参考了官方题解和力扣的题解。

其实问题没那么复杂，只是自己没想透彻。本质上就是一个回溯暴力搜索。对于每一个开局情况，我们就试试所有的选择，看是不是能有一个能赢。就是傻傻的试。

对于使用过的数字，因为题目里提到最多 20 个，而且又不重复。所以可以很巧妙的使用一个 int 内的 bit 来表达各个数的使用情况。这样还可以直接方便的用 pass-by-value，就不用自己显式的来做回溯操作了。

代码

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        // special case
        if (maxChoosableInteger >= desiredTotal)
            return true;
        // total sum of all numbers cannot reach the desiredTotal
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
            return false;

        unordered_set<int> used;
        unordered_map<int, bool> memo;

        return dfs(maxChoosableInteger, desiredTotal, 0, memo);
    }

    bool dfs(const int maxChoosableInteger, const int desiredTotal, int used, unordered_map<int, bool>& memo)
    {
        if (memo.find(used) != memo.end())
            return memo[used];

        for (int i = 1; i <= maxChoosableInteger; i++) {
            // use bit to show if one number is used
            int this_n = 1 << (i - 1);
            if (used & this_n)
                continue;

            // assume we choice this number, to see if we can win
            if (i >= desiredTotal || !dfs(maxChoosableInteger, desiredTotal - i, this_n | used, memo)) {
                return memo[used] = true;
            }
        }

        return memo[used] = false;
    }
};

复杂度分析

时间：O(2^n), n 是题目中的可选最大值。每个数都有选和不选两种情况。
空间：O(2^n)

z1ggy-o commented 2 years ago

思路

参考了官方题解和力扣的题解。

其实问题没那么复杂，只是自己没想透彻。本质上就是一个回溯暴力搜索。对于每一个开局情况，我们就试试所有的选择，看是不是能有一个能赢。就是傻傻的试。

对于使用过的数字，因为题目里提到最多 20 个，而且又不重复。所以可以很巧妙的使用一个 int 内的 bit 来表达各个数的使用情况。这样还可以直接方便的用 pass-by-value，就不用自己显式的来做回溯操作了。

代码

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        // special case
        if (maxChoosableInteger >= desiredTotal)
            return true;
        // total sum of all numbers cannot reach the desiredTotal
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
            return false;

        unordered_set<int> used;
        unordered_map<int, bool> memo;

        return dfs(maxChoosableInteger, desiredTotal, 0, memo);
    }

    bool dfs(const int maxChoosableInteger, const int desiredTotal, int used, unordered_map<int, bool>& memo)
    {
        if (memo.find(used) != memo.end())
            return memo[used];

        for (int i = 1; i <= maxChoosableInteger; i++) {
            // use bit to show if one number is used
            int this_n = 1 << (i - 1);
            if (used & this_n)
                continue;

            // assume we choice this number, to see if we can win
            if (i >= desiredTotal || !dfs(maxChoosableInteger, desiredTotal - i, this_n | used, memo)) {
                return memo[used] = true;
            }
        }

        return memo[used] = false;
    }
};

复杂度分析

时间：O(2^n), n 是题目中的可选最大值。每个数都有选和不选两种情况。
空间：O(2^n)

machuangmr commented 2 years ago

代码

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if(maxChoosableInteger >= desiredTotal) return true;
        if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;

        return dfs(0, desiredTotal, new Boolean[1 << maxChoosableInteger], maxChoosableInteger);
    }

    private boolean dfs(int state, int desiredTotal, Boolean[] dp, int maxChoosableInteger){
        if(dp[state] != null){
            return dp[state];
        }

        for(int i = 1; i <= maxChoosableInteger; i++){
            int cur = 1 << (i - 1);
            if((cur & state) != 0){
                continue;
            }

            if(i >= desiredTotal || !dfs(cur|state, desiredTotal - i, dp, maxChoosableInteger)){
                return dp[state] = true;
            }
        }
        return dp[state] = false;
    }
}

charlestang commented 2 years ago

思路

回溯法

对于每个数字，如果拿了能赢，那么就是可以赢。
拿了赢不了，但是对方如果无法赢，那么我也可以赢。

否则就会输掉

代码

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if maxChoosableInteger >= desiredTotal: return True
        if (1 + maxChoosableInteger) * maxChoosableInteger < 2 * desiredTotal: return False

        visited = [False] * (maxChoosableInteger + 1)
        def dfs(t: int) -> bool:
            for i in range(1, maxChoosableInteger + 1):
                if visited[i]: continue
                if t + i >= desiredTotal: return True
                visited[i] = True
                if not dfs(t + i):
                    visited[i] = False
                    return True
                visited[i] = False
            return False
        return dfs(0)

fornobugworld commented 2 years ago

class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool: if maxChoosableInteger >= desiredTotal: return True if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal: return False

    def dfs(state, desiredTotal, dp):
        if dp[state] != None:
            return dp[state]
        for i in range(1, maxChoosableInteger + 1):
            cur = 1 << (i - 1)
            if cur & state != 0:
                continue

            if i >= desiredTotal or not dfs(cur | state, desiredTotal - i, dp):
                dp[state] = True
                return True
        dp[state] = False
        return False

    return dfs(0, desiredTotal, [None] * (1 << maxChoosableInteger))

taojin1992 commented 2 years ago

/*
# Logic:
boolean dp[state]: 
can we win when in state for target? 

1 <= maxChoosableInteger <= 20
Use an integer 32 bit to represent the state
1-> 00000000 00000000 00000000 00000010

If maxChoosableInteger=1
10

[1, maxChoosableInteger]

Assuming using i from [1, maxChoosableInteger]
current state becomes 
previous state ^ (1 << i)
new target = target - i

a^b^a = b 

# Complexity:

*/

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        // edge case: 1st will win
        if (desiredTotal <= 0) return true;
        // extract all < target
        if ((1 + maxChoosableInteger) * maxChoosableInteger < 2 * desiredTotal) {
            return false;
        }

        int[] dp = new int[1 << maxChoosableInteger];

        return dfs(dp, desiredTotal, 0, maxChoosableInteger);
    }

    private boolean dfs(int[] dp, int target, int state, int maxChoosableInteger) {
        if (target <= 0) return false; // 2nd player reach or exceed the target
        if (dp[state] != 0) { 
            // if 1 we can win at current state given the target
            // if -1 lose, 0 means not computed
            return dp[state] == 1;
        }
        boolean win = false;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            // check if the current i used
            // if i = 1, 1 << i = 10 (2)
            // cur state = 10

            if ((state & (1 << (i - 1))) == 0) {
                win = win || !dfs(dp, target - i, state ^ (1 << (i - 1)), maxChoosableInteger);
            }
        }

        dp[state] = win ? 1 : -1;
        return win;
    }

}

for123s commented 2 years ago

··· class Solution { public: bool dfs(int maxChoosableInteger, int desiredTotal, int state, vector& dp) { if(dp[state]<2) return bool(dp[state]); for(int i=1;i<=maxChoosableInteger;i++) { int temp = (1<<(i-1)); if(temp&state) continue; if(desiredTotal-i<=0||!dfs(maxChoosableInteger, desiredTotal-i, state|temp,dp)) { dp[state] = 1; return true; } } dp[state] = 0; return false; }

bool canIWin(int maxChoosableInteger, int desiredTotal) {
    if(maxChoosableInteger>=desiredTotal)
        return true;
    if((1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal)
        return false;
    vector<int> dp(1<<maxChoosableInteger,2);
    return dfs(maxChoosableInteger, desiredTotal, 0, dp);
}

}; ···

bluetomlee commented 2 years ago

public class Solution {

    /**
     * 记忆化回溯（也称为递归+备忘录），自顶向下
     * 采用记忆化后的时间复杂度为O(2^n)(如果不进行记忆的话，时间复杂度将是O(n!))，可以理解为已经缩成了只有一个分支了
     * 然后为什么要进行记忆化：
     * 因为我们发现，例如[2,3]和[3,2]之后的玩家选择状态都是一样的，都是可以从除了2,3之外的
     * 数字进行选择，那么就可以对选择2和3后第一个玩家能不能赢进行记忆存储
     * 这里采用state[]数组存储每个数字是否都被选过，选过则记录为1，然后我们将state.toString()
     * 使得[2,3]和[3,2]它们的结果都是一样的"0011"，作为key，存储在HashMap中，value是选了2和3
     * 之后第一个玩家是否稳赢
     * @param maxChoosableInteger
     * @param desiredTotal
     * @return
     */
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false; //1,..maxChoosable数列总和都比目标和小
        int[] state = new int[maxChoosableInteger + 1];  //state[1]=1表示1被选了

        return backtraceWitMemo(state, desiredTotal, new HashMap<String, Boolean>());
    }

    private boolean backtraceWitMemo(int[] state, int desiredTotal, HashMap<String, Boolean> map) {
        String key = Arrays.toString(state); //这里比较关键，如何表示这个唯一的状态，例如[2,3]和[3,2]都是"0011"，状态一样
        if (map.containsKey(key)) return map.get(key);  //如果已经记忆了这样下去的输赢结果,记忆是为了防止如[2,3]，[3,2]之后的[1,4,5,..]这个选择区间被重复计算

        for (int i = 1; i < state.length; i++){
            if (state[i] == 0){ //如果这个数字i还没有被选中
                state[i] = 1;
                //如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了
                if (desiredTotal - i <= 0 || !backtraceWitMemo(state, desiredTotal - i, map)) {
                    map.put(key, true);
                    state[i] = 0; //在返回之前回溯
                    return true;
                }
                //如果不能赢也要记得回溯
                state[i] = 0;
            }
        }
        //如果都赢不了
        map.put(key, false);
        return false;
    }
}

cszys888 commented 2 years ago

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if (maxChoosableInteger+1)*maxChoosableInteger/2 < desiredTotal:
            return False

        dp = [None]*(2**maxChoosableInteger)

        def dfs(state, total, dp):
            if dp[state] != None:
                return dp[state]
            for i in range(1,maxChoosableInteger+1):
                cur = 1 << (i-1)
                if cur & state != 0:
                    continue
                else:
                    if i >= total or not dfs(cur | state, total - i, dp):
                        dp[state] = True
                        return True
            dp[state] = False
            return False
        return dfs(0, desiredTotal, dp)

time complexity: O(2^N) space complexity: O(2^N)

leetcode-pp / 91alg-6-daily-check

【Day 60 】2022-02-09 - 464. 我能赢么 #70

464. 我能赢么

入选理由

题目地址

前置知识

题目描述

Idea

Code

Complexity

思路

思路

代码

复杂度分析

题解都看不明白， 先抄个答案吧

思路

关键点

代码

思路

代码

复杂度分析

思路

思路

代码

代码

复杂度

思路

代码

思路

代码

复杂度分析

看题解

思路

代码

复杂度

思路

代码

复杂度

picked 用于保存当前已经选择过的数。

思路

代码

代码

Codes

picked 用于保存当前已经选择过的数。

思路

代码

思路

代码

代码

思路

代码

题解都看不明白，先抄个答案吧