2021-12-03：石子遊戲 IV。Alice 和 Bob 兩個人輪流玩一個

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代碼