2021-12-03：石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。 一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平

2021-12-03：石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
来自力扣1510。
来自哈喽单车。

答案2021-12-03：

动态规划。
时间复杂度：O(N*sqrt(N))。
额外空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import (

    "fmt"

    "math"

)

func main() {

    for i := 1; i <= 100; i++ {

        ret := winnerSquareGame3(i)

        ret2 := numSquares(i)

        fmt.Println(i, ret, ret2)

    }

}

func winnerSquareGame3(n int) bool {

    dp := make([]bool, n+1)

    for i := 1; i <= n; i++ {

        for j := 1; j*j <= i; j++ {

            if !dp[i-j*j] {

                dp[i] = true

                break

            }

        }

    }

    return dp[n]

}

// 判断是否为完全平方数

func isPerfectSquare(x int) bool {

    y := int(math.Sqrt(float64(x)))

    return y*y == x

}

// 判断是否能表示为 4^k*(8m+7)

func checkAnswer4(x int) bool {

    for x%4 == 0 {

        x /= 4

    }

    return x%8 == 7

}

func numSquares(n int) int {

    if isPerfectSquare(n) {

        return 1

    }

    if checkAnswer4(n) {

        return 4

    }

    for i := 1; i*i <= n; i++ {

        j := n - i*i

        if isPerfectSquare(j) {

            return 2

        }

    }

    return 3

}

执行结果如下：

左神java代码

2021-12-03：石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。 一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平的相关教程结束。