golang刷leetcode：我能贏嗎

在 "100 game" 這個游戲中，兩名玩家輪流選擇從 1 到 10 的任意整數(shù)，累計整數(shù)和，先使得累計整數(shù)和 達(dá)到或超過  100 的玩家，即為勝者。

如果我們將游戲規(guī)則改為 “玩家 不能 重復(fù)使用整數(shù)” 呢？

例如，兩個玩家可以輪流從公共整數(shù)池中抽取從 1 到 15 的整數(shù)（不放回），直到累計整數(shù)和 >= 100。

給定兩個整數(shù) maxChoosableInteger （整數(shù)池中可選擇的最大數(shù)）和 desiredTotal（累計和），若先出手的玩家是否能穩(wěn)贏則返回 true ，否則返回 false 。假設(shè)兩位玩家游戲時都表現(xiàn) 最佳 。

示例 1：

輸入：maxChoosableInteger = 10, desiredTotal = 11

輸出：false

解釋：

無論第一個玩家選擇哪個整數(shù)，他都會失敗。

第一個玩家可以選擇從 1 到 10 的整數(shù)。

如果第一個玩家選擇 1，那么第二個玩家只能選擇從 2 到 10 的整數(shù)。

第二個玩家可以通過選擇整數(shù) 10（那么累積和為 11 >= desiredTotal），從而取得勝利.

同樣地，第一個玩家選擇任意其他整數(shù)，第二個玩家都會贏。

示例 2:

輸入：maxChoosableInteger = 10, desiredTotal = 0

輸出：true

示例 3:

輸入：maxChoosableInteger = 10, desiredTotal = 1

輸出：true

提示:

1 <= maxChoosableInteger <= 20

0 <= desiredTotal <= 300

解題思路：

1，如果可以重復(fù)放回，就是一個簡單遞歸

2，本題是不能放回，那就需要一個位圖記錄已經(jīng)使用的數(shù)字，并且需要一個變量記錄當(dāng)前的和

3，能贏的前提是，找不出任意一個數(shù)字使得對手可以贏。

代碼實(shí)現(xiàn)

func canIWin(maxChoosableInteger, desiredTotal int) bool {    if (1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal {        return false    }
    dp := make([]int8, 1<<maxChoosableInteger)    for i := range dp {        dp[i] = -1    }    var dfs func(int, int) int8    dfs = func(usedNum, curTot int) (res int8) {        dv := &dp[usedNum]        if *dv != -1 {            return *dv        }        defer func() { *dv = res }()        for i := 0; i < maxChoosableInteger; i++ {            if usedNum>>i&1 == 0 && (curTot+i+1 >= desiredTotal || dfs(usedNum|1<<i, curTot+i+1) == 0) {                return 1            }        }        return    }    return dfs(0, 0) == 1}

推薦閱讀

• golang刷leetcode：巫師的總力量和