LeetCode-1510 石子游戏 IV

Table of Contents

LeetCode-1510 石子游戏 IV #

Solution 1 #

$dp[i]$ 代表从 $i$ 开始取先手是否必胜, 递归.

代码如下:

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        @cache
        def f(x):
            if x <= 1:
                return x == 1
            for i in range(1, int(sqrt(x)) + 2):
                if i ** 2 <= x:
                    if f(x - i ** 2) == False:
                        return True
            return False
        return f(n)