【Day 60 】2023-04-14 - 464. 我能赢么

[azl397985856]

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

[Zoeyzyzyzy]

class Solution {
    // improvement 1: 用一个int state来标识公共整数池的使用情况 instead of set to avoid copy &
    // maxChoosableInteger space
    int maxChoosableInteger, desiredTotal;
     // 用state来标记整个公共整数池的使用情况，eg: state = 0 -> binary:0 没有数字被用过； state = 18 -> 10010 表示1和4已经被用过了
    // visted[i] = 0 未被访问， visited[i] = 1 访问过，为true, visited[i] = 2 访问过，为false
    int[] visited = new int[1 << 21];

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

    private boolean dfs(int state, int sum) {
        if (visited[state] == 1)
            return true;
        if (visited[state] == 2)
            return false;
        for (int x = 1; x <= maxChoosableInteger; x++) {
            // x已经被选过了
            if (((1 << x) & state) != 0)
                continue;
            if (x + sum >= desiredTotal) {
                visited[state] = 1;
                return true;
            }
            // 对方一定会输吗？
            if (!dfs((1 << x) | state, sum + x)) {
                visited[state] = 1;
                return true;
            }
        }
        visited[state] = 2;
        return false;
    }
}

[JiangyanLiNEU]

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

        memo = {}
        choices = [i for i in range(1, maxi+1)]

        def dp(left, subTarget):
            if left[-1] >= subTarget:
                return True
            if tuple(left) in memo:
                return memo[tuple(left)]
            for i in range(len(left)):
                newLeft = left[:i] + left[i+1:]
                if not dp(newLeft, subTarget-left[i]):
                    memo[tuple(left)] = True
                    return True
            memo[tuple(left)] = False
            return False
        return dp(choices, target)

[tzuikuo]

思路

动态规划

代码

bool canIWin(int M, int T) 
  {
    int sum = M*(M+1)/2; // sum of entire choosable pool

    // I just pick 1 to win
    if (T < 2) return true;

    // Total is too large, nobody can win
    else if (sum < T) return false;

    // Total happens to match sum, whoever picks at odd times wins
    else if (sum == T) return M%2;

    // Non-trivial case: do DFS
    // Initial total: T
    // Initial game state: k = 0 (all numbers are not picked)
    else return dfs(M, T, 0);
  }

  // DFS to check if I can win
  // k: current game state
  // T: remaining total to reach
  bool dfs(int M, int T, int k) 
  {
    // memorized
    if (mem[k] != 0) return mem[k] > 0;

    // total is already reached by opponent, so I lose
    if (T <= 0) return false;

    // try all currently available numbers
    for (int i = 0; i < M; ++i)
      // if (i+1) is available to pick and my opponent can't win after I picked, I win!
      if (!(k&(1<<i)) && !dfs(M, T-i-1, k|(1<<i))) {
        mem[k] = 1;
        return true;
      } 

    // Otherwise, I will lose
    mem[k] = -1;
    return false;      
  }

  // m[key]: memorized game result when pool state = key
  // 0: un-computed; 1: I win; -1: I lose
  int mem[1<<20] = {};

复杂度分析

• 时间复杂度：O(m*n)
• 空间复杂度：O(m*n)

[kofzhang]

思路

动态规划

复杂度

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

代码

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

        def helper(state,remainTotal,dp):
            if dp[state]!=None:
                return dp[state]
            for i in range(1,maxChoosableInteger+1):
                ch = 1<<(i-1)
                if ch & state !=0:  # 已经被选过了
                    continue
                if i>=remainTotal:  # 如果再直接选一张就能赢，则当前状态一定赢
                    dp[state] = True
                    return True
                if not helper(ch | state,remainTotal-i,dp):  # 如果对方选牌没有赢
                    dp[state] = True
                    return True
            dp[state]=False  # 不能赢就肯定输
            return False

        return helper(0,desiredTotal,[None]*(2**maxChoosableInteger-1))

[joemonkeylee]

思路

DFS

代码

    Dictionary<int, bool> memo = new Dictionary<int, bool>();

    public bool CanIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        return DFS(maxChoosableInteger, 0, desiredTotal, 0);
    }

    public bool DFS(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {
        if (!memo.ContainsKey(usedNumbers)) {
            bool res = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((usedNumbers >> i) & 1) == 0) {
                    if (i + 1 + currentTotal >= desiredTotal) {
                        res = true;
                        break;
                    }
                    if (!DFS(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {
                        res = true;
                        break;
                    }
                }
            }
            memo.Add(usedNumbers, res);
        }
        return memo[usedNumbers];
    }

复杂度分析

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

[Diana21170648]

思路

动态规划+位移运算状态压缩

class Slution:
    def caniwin(self,max:int,total:int)->bool:
        #第一种特殊情况
        if max>=total:
            return True #谁第一个选谁赢
        #第二种特殊情况
        if sum(range(max+1))<=total:
            return False #求和都不会大于给定值，两个人都不可能赢
    #进行位移运算，状态压缩
    def dp(self, picked, accelerate, total:int):
        if accelerate>=total:
            if picked==(1<<(max+1))-1:
                return False
            for n in range(1,max+1):
                if picked & 1<<n==0:
                    #如果没有被选择，且会超过total，则现在选择的玩家赢
                    if not dp(picked| 1<<n,accelerate+n):
                        return True
                    return False
                return dp(0,0)

**复杂度分析**
- 时间复杂度：O(max*N)，其中 N 为节点数。
- 空间复杂度：O(2^N)

[xb798298436]

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;
}

}

[Abby-xu]

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

        return ((1 + maxChoosableInteger) * maxChoosableInteger) >> 1 >= desiredTotal and dfs(0, 0)

[huizsh]

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)

[RestlessBreeze]

code

class Solution {
public:
    int res[1 << 21];
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
            return false;
        if (maxChoosableInteger >= desiredTotal)
            return true;

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

    bool dfs(int used, int cursum, int maxChoosableInteger, int desiredTotal)
    {
        if (res[used] == 1)
            return true;
        if (res[used] == 2)
            return false;
        for (int i = 1; i < maxChoosableInteger + 1; i++)
        {
            if (1 << i & used)
                continue;
            if (cursum + i >= desiredTotal)
            {
                res[used] = 1;
                return true;
            }  
            if (!dfs(1 << i | used, cursum + i, maxChoosableInteger, desiredTotal))
            {
                res[used] = 1;
                return true;
            }  
        }
        res[used] = 2;
        return false;
    }
};

[FireHaoSky]

思路：动态规划，对于记录且累加的问题，有限长度，使用二进制存储结果，递归进行遍历

代码：python

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

        def dfs(state, sum):
            if visited[state] == 1:
                return True
            if visited[state] == 2:
                return False
            for x in range(1, maxChoosableInteger+1):
                if (1<<x) & state:
                    continue
                if sum + x >= desiredTotal:
                    visited[state] = 1
                    return True
                if not dfs((1<<x) | state, sum + x):
                    visited[state]=1
                    return True
            visited[state] = 2
            return False
        return dfs(0,0)

复杂度分析：

"""
时间复杂度：O(m*2^m)
空间复杂度：O(2^m)
"""

[zhangyu1131]

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

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

private:
    bool dfs(int maxChoosableInteger, int usedNumbers/*每一位表示是否被使用过*/, int desiredTotal, int tmp_total)
    {
        if (mem_map.find(usedNumbers) == mem_map.end())
        {
            int res = false;
            for (int i = 1; i <= maxChoosableInteger; ++i)
            {
                if ((usedNumbers & (1 << i)) == 0) // i还没被用过，&优先级比==低，所以括号不能省
                {
                    if (tmp_total + i >= desiredTotal)
                    {
                        res = true;
                        break;
                    }
                    // 如果选了i还不能直接赢，就判断一下A这次选了i之后，B会不会输，如果B会输，那就A赢
                    if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, tmp_total + i))
                    {
                        res = true;
                        break;
                    }
                }
            }
            mem_map[usedNumbers] = res;
        }
        return mem_map[usedNumbers];
    }

private:
    unordered_map<int, bool> mem_map;
};

[harperz24]

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(used, cur_total):
            if cur_total >= desiredTotal:
                return False
            if used == (1 << (maxChoosableInteger + 1)) - 1:
                return False
            for n in range(1, maxChoosableInteger + 1):
                if used & 1 << n == 0:
                    if not dp(used | 1 << n, cur_total + n):
                        return True
            return False

        return dp(0, 0)

[wangzh0114]

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;
    }
};

[Size-of]

var canIWin = function(maxChoosableInteger, desiredTotal) { const memo = new Map(); const dfs = (maxChoosableInteger, usedNumbers, desiredTotal, currentTotal) => { if (!memo.has(usedNumbers)) { let res = false; for (let i = 0; i < maxChoosableInteger; i++) { if (((usedNumbers >> i) & 1) === 0) { if (i + 1 + currentTotal >= desiredTotal) { res = true; break; } if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) { res = true; break; } } } memo.set(usedNumbers, res); } return memo.get(usedNumbers); } if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) { return false; } return dfs(maxChoosableInteger, 0, desiredTotal, 0); };

[kangliqi1]

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;
}

}

[KrabbeJing]

代码

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

        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)

[bookyue]

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

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;

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

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

    private boolean dfs(int state, int sum, int maxChoosableInteger, int desiredTotal, byte[] visited) {
        if (visited[state] == 1) return true;
        if (visited[state] == 2) return false;

        for (int num = 1; num <= maxChoosableInteger; num++) {
            if (((state >> num) & 1) == 1) continue;

            if (sum + num >= desiredTotal) {
                visited[state] = 1;
                return true;
            }

            if (!dfs((state | 1 << num), sum + num, maxChoosableInteger, desiredTotal, visited)) {
                visited[state] = 1;
                return true;
            }

            visited[state] = 2;
        }

        visited[state] = 2;
        return false;
    }

[lp1506947671]

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)

[JasonQiu]

• DFS

  class Solution:
  def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
      if maxChoosableInteger >= desiredTotal:
          return True
      if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:
          return False
      visited = defaultdict(int)
  
      def dfs(state, sum):
          if visited[state] == 1:
              return True
          if visited[state] == 2:
              return False
          for number in range(1, maxChoosableInteger + 1):
              if (1 << number) & state:
                  continue
              if sum + number >= desiredTotal:
                  visited[state] = 1
                  return True
              if not dfs((1 << number) | state, sum + number):
                  visited[state] = 1
                  return True
          visited[state] = 2
          return False
  
      return dfs(0, 0)

  Time: O(m*2^m) Space: O(2^m)

[snmyj]

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if (maxChoosableInteger + 1) * maxChoosableInteger // 2 < desiredTotal:
            return False
        if desiredTotal <= 0:
            return True
        memo = {}
        def dfs(used, cur_total):
            if cur_total <= 0:
                return False
            if used in memo:
                return memo[used]
            for i in range(maxChoosableInteger):
                if not used & (1 << i):
                    if not dfs(used | (1 << i), cur_total - i - 1):
                        memo[used]

[Jetery]

class Solution {
public:
    bool canIWin(int M, int T) {
        const int sum = M * (M + 1) / 2;
        if (sum < T) return false;
        if (T == 0) return true;
        m_ = vector<char>(1 << M, 0);
        return dfs(M, T, 0);
    }

private:
    vector<char> m_; // 0: unknown, 1: won, -1: lost
    bool dfs(int M, int T, int state) {
        if (T <= 0) return false;
        if (m_[state]) return m_[state] == 1;
        for (int i = 0; i < M; ++i) {
            if (state & (1 << i)) continue; // number i used      
            // The next player can not win, current player wins
            if (!dfs(M, T - (i + 1), state | (1 << i))) 
                //return m_[state] = 1;
                return true;
        }
        // Current player loses.
        m_[state] = -1;
        return false;
    }
};

[Lydia61]

464. 我能赢么

思路

动态规划

代码

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))

复杂度分析

• 时间复杂度：O(m*2^m)
• 空间复杂度：O(2^m)

[X1AOX1A]

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)

[enrilwang]

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

    memo = {}
    choices = [i for i in range(1, maxi+1)]

    def dp(left, subTarget):
        if left[-1] >= subTarget:
            return True
        if tuple(left) in memo:
            return memo[tuple(left)]
        for i in range(len(left)):
            newLeft = left[:i] + left[i+1:]
            if not dp(newLeft, subTarget-left[i]):
                memo[tuple(left)] = True
                return True
        memo[tuple(left)] = False
        return False
    return dp(choices, target)

[chanceyliu]

代码

function canIWin(maxChoosableInteger: number, desiredTotal: number): boolean {
  const memo = new Map();
  const dfs = (
    maxChoosableInteger,
    usedNumbers,
    desiredTotal,
    currentTotal
  ) => {
    if (!memo.has(usedNumbers)) {
      let res = false;
      for (let i = 0; i < maxChoosableInteger; i++) {
        if (((usedNumbers >> i) & 1) === 0) {
          if (i + 1 + currentTotal >= desiredTotal) {
            res = true;
            break;
          }
          if (
            !dfs(
              maxChoosableInteger,
              usedNumbers | (1 << i),
              desiredTotal,
              currentTotal + i + 1
            )
          ) {
            res = true;
            break;
          }
        }
      }
      memo.set(usedNumbers, res);
    }
    return memo.get(usedNumbers);
  };
  if (((1 + maxChoosableInteger) * maxChoosableInteger) / 2 < desiredTotal) {
    return false;
  }
  return dfs(maxChoosableInteger, 0, desiredTotal, 0);
}

[enrilwang]

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

    memo = {}
    choices = [i for i in range(1, maxi+1)]

    def dp(left, subTarget):
        if left[-1] >= subTarget:
            return True
        if tuple(left) in memo:
            return memo[tuple(left)]
        for i in range(len(left)):
            newLeft = left[:i] + left[i+1:]
            if not dp(newLeft, subTarget-left[i]):
                memo[tuple(left)] = True
                return True
        memo[tuple(left)] = False
        return False
    return dp(choices, target)