# Python concise DP solution + hard-coded

• You win if you can move into a position where your opponent looses.

``````class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
memo = {}
def win(v, n):
if not v: return False
if v[-1] >= n: return True
ans = memo.get(v)
if ans == None:
ans = memo[v] = any(not win(v[:i]+v[i+1:], n-x) for i, x in enumerate(v))
return ans
m, n = maxChoosableInteger, desiredTotal
return n <= m*(m+1)//2 and win(tuple(range(1, m+1)), n)
``````

Of course a really fast solution hard-codes the answer :).

``````class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
loose = [
[],
[],
[3],
[4],
[5, 9, 10],
[6, 11],
[7, 14, 18, 19, 20, 21],
[8, 15, 22],
[9, 18, 22, 25, 27, 31, 32, 33, 34, 35, 36],
[10, 19, 26, 28, 37],
[11, 22, 27, 33, 37, 40, 42, 44, 48, 49, 50, 51, 52, 53, 54, 55],
[12, 23, 24, 28, 34, 36, 41, 43, 45, 56],
[13, 25, 26, 30, 33, 39, 42, 44, 45, 52, 56, 58, 59, 60, 61, 63, 65, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78],
[14, 27, 34, 40, 53, 59, 62, 64, 66, 79],
[15, 30, 34, 35, 45, 52, 53, 60, 63, 65, 66, 69, 75, 79, 81, 82, 83, 84, 85, 86, 88, 90, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105],
[16, 31, 32, 36, 46, 61, 66, 70, 71, 76, 87, 89, 91, 106],
[17, 33, 34, 38, 51, 59, 68, 71, 72, 76, 85, 88, 90, 91, 93, 102, 106, 108, 109, 110, 111, 112, 113, 114, 115, 117, 119, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136],
[18, 35, 52, 53, 54, 69, 70, 71, 74, 75, 86, 91, 92, 94, 97, 98, 103, 112, 113, 116, 118, 120, 137],
[19, 38, 42, 55, 57, 60, 65, 76, 95, 99, 102, 114, 117, 119, 120, 122, 123, 124, 125, 133, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 150, 152, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171],
[20, 39, 40, 58, 69, 77, 78, 81, 96, 100, 103, 104, 115, 119, 123, 124, 125, 128, 129, 134, 145, 146, 149, 151, 153, 172],
[21, 41, 42, 46, 63, 84, 94, 95, 104, 105, 109, 126, 129, 130, 132, 133, 134, 147, 150, 152, 153, 155, 156, 158, 168, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 187, 189, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210],
]
m, n = maxChoosableInteger, desiredTotal
return n <= m*(m+1)//2 and not n in loose[m]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.