題目

核心思路

這道題思考了挺長(zhǎng)的時(shí)間，卻始終沒有想到解決方案，主要是題目中兩位玩家游戲時(shí)都表現(xiàn)最佳感覺表示不出來，看了這位大佬的深搜之后豁然開朗。
我之前主要的疑惑是怎么只用一個(gè)搜索函數(shù)就同時(shí)表示出兩個(gè)玩家的游戲勝負(fù)，因?yàn)檫@一輪是我在選數(shù)，返回的結(jié)果也是我是否能取勝；而下一輪就是對(duì)手選數(shù)及能否取勝了(其實(shí)現(xiàn)在想來，傳參是傳入一個(gè)標(biāo)識(shí)位也是可行的)。在深搜代碼中，還是有部分挺值得思考的。

  public boolean dfs(int desiredTotal, boolean[] visited){
        if(desiredTotal <= 0) return false;
        for(int i = 1; i < visited.length; i++){
            if(!visited[i]){
                visited[i] = true;
                boolean tmp = dfs(desiredTotal - i, visited);
                visited[i] = false;
                if(!tmp) return true;
            }
        }
        return false;
    }

代碼中的 visited數(shù)組 表示的是1-max是否被取過了。而代碼的主要部分

        if(!visited[i]){
            visited[i] = true;
            boolean tmp = dfs(desiredTotal - i, visited);
            visited[i] = false;
            if(!tmp) return true;
        }

并不是記錄先手的人贏還是后手的人贏，而是返回當(dāng)前輪游戲中，游戲人(先手的或者后手的)是否能穩(wěn)贏，這樣本輪游戲人(以下以 我 代稱)又可以得到下一輪游戲人(以下以 對(duì)手 代稱)的游戲結(jié)果dfs(desiredTotal - i, visited)。這里有兩種情況，我 取了 i 這個(gè)整數(shù)后，要么 對(duì)手 可以穩(wěn)贏，要么 對(duì)手 不能穩(wěn)贏。而其中 對(duì)手 不能穩(wěn)贏也就意味著在他那一輪游戲中出現(xiàn)了 我 可以穩(wěn)贏的情況。
這里要先回溯在返回，因?yàn)?我 并不是特指先手玩家或者后手玩家，我 只是本輪的游戲玩家，而且我 要做出最優(yōu)的游戲選擇，所以 我 就要在所有剩余的取數(shù)情況中找到 對(duì)手 可以穩(wěn)輸?shù)那闆r，這樣 我 就穩(wěn)贏了，所以有 if(!tmp) return true; 這樣一行代碼，對(duì)手穩(wěn)輸情況返回true，而 我 的返回值又會(huì)交給上一輪的 對(duì)手 來考慮策略，這樣就可以保證雙方都能做出最優(yōu)的選擇，而不會(huì)某一輪游戲中一名玩家找到最優(yōu)解就直接一路return到第一輪游戲。

狀壓DP

通過上邊的深搜，其實(shí)不難發(fā)現(xiàn)：如果在某次游戲中的某輪游戲中，前面取了[1,2,3]和[2,1,3]對(duì)本輪游戲是否穩(wěn)贏沒有影響，因?yàn)樗麄兊暮投紴?，也就是下一輪都要執(zhí)行 dfs(desiredTotal - 6 - i, visited)，這里的 i 和上邊一樣用來遍歷沒取過的數(shù) i。也就是說對(duì)于同一個(gè)已經(jīng)取走數(shù)的集合([1,2,3]與[2,1,3])，由于剩下的desiredTotal也是相同的，故dfs方法給出的結(jié)果也是相同。這樣就有了很多重復(fù)計(jì)算的過程，考慮使用一個(gè)memo數(shù)組記錄也就理所應(yīng)當(dāng)了。
因?yàn)閷?duì)于每一個(gè)數(shù)只有取了或者沒取兩種狀態(tài)，而且對(duì)于同一個(gè)狀態(tài)，取的順序并不影響結(jié)果。所以可以想到使用狀態(tài)壓縮DP來記錄每一種狀態(tài)。

完整代碼

剩下的就是很典型的狀壓DP計(jì)算方法了。

class Solution {

    Boolean[] memo = new Boolean[1 << 20];

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        //先取穩(wěn)贏
        if(maxChoosableInteger >= desiredTotal) return true;
        //兩人都不能贏
        if(((1 + maxChoosableInteger) * maxChoosableInteger / 2) < desiredTotal) return false;
        
        return dfs(maxChoosableInteger, desiredTotal, 0);
    }

    public boolean dfs(int max, int desiredTotal, int state){
        if(memo[state] != null) return memo[state];
        
        for(int i = 0; i < max; i++){
            int tmp = 1 << i;
            if((tmp & state) == 0){
                //我這輪穩(wěn)贏或者對(duì)面下一輪穩(wěn)輸
                if(desiredTotal <= i + 1 || !dfs(max, desiredTotal - i - 1, state | tmp)){
                    memo[state] = true;
                    return true;
                }
            }
        }
        memo[state] = false;
        return false;
    }
}

對(duì)于位運(yùn)算部分：int tmp = 1 << i; temp & state，通過tmp取到當(dāng)前狀態(tài)state是否取到了i + 1這個(gè)數(shù)，我遍歷從零開始主要是移位的時(shí)候舒服一點(diǎn)。state | tmp 就是在 state 的基礎(chǔ)上取 i + 1 這個(gè)數(shù)。

總結(jié)

雖然方法叫狀態(tài)壓縮DP，其實(shí)只是一種枚舉的方式，所以主要還是要看數(shù)據(jù)范圍是否能承受O(2^N)的時(shí)間復(fù)雜度，對(duì)于數(shù)據(jù)范圍小于等于30 的問題還是比較好用的，剩下最重要的就是要理解題目的意思了。
如果有寫的不正確的地方還請(qǐng)指出，感恩相遇~