Python concise DP solution + hard-coded


  • 0
    L

    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]
    

Log in to reply
 

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