狀壓 DP 是什么？這篇題解帶你入門

題目地址（464. 我能贏么）

https://leetcode-cn.com/problems/can-i-win/

題目描述

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

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

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

給定一個整數 maxChoosableInteger （整數池中可選擇的最大數）和另一個整數 desiredTotal（累計和），判斷先出手的玩家是否能穩(wěn)贏（假設兩位玩家游戲時都表現(xiàn)最佳）？

你可以假設 maxChoosableInteger 不會大于 20， desiredTotal 不會大于 300。

示例：

輸入：
maxChoosableInteger?=?10
desiredTotal?=?11

輸出：
false

解釋：
無論第一個玩家選擇哪個整數，他都會失敗。
第一個玩家可以選擇從 1 到 10?的整數。
如果第一個玩家選擇 1，那么第二個玩家只能選擇從 2 到 10?的整數。
第二個玩家可以通過選擇整數?10（那么累積和為?11?>=?desiredTotal），從而取得勝利.
同樣地，第一個玩家選擇任意其他整數，第二個玩家都會贏。

前置知識

• 動態(tài)規(guī)劃^[1]
• 回溯

公司

• 阿里
• linkedin

暴力解（超時）

思路

題目的函數簽名如下：

def?canIWin(self,?maxChoosableInteger:?int,?desiredTotal:?int)?->?bool:

即給你兩個整數 maxChoosableInteger 和 desiredTotal，讓你返回一個布爾值。

兩種特殊情況

首先考慮兩種特殊情況，后面所有的解法這兩種特殊情況都適用，因此不再贅述。

• 如果 desiredTotal 是小于等于 maxChoosableInteger 的，直接返回 True，這不難理解。
• 如果 [1, maxChoosableInteger] 全部數字之和小于 desiredTotal，誰都無法贏，返回 False。

一般情況

考慮完了特殊情況，我們繼續(xù)思考一般情況。

首先我們來簡化一下問題， 如果數字可以隨便選呢？這個問題就簡單多了，和爬樓梯沒啥區(qū)別。這里考慮暴力求解，使用 DFS + 模擬的方式來解決。

注意到每次可選的數字都不變，都是 [1, maxChoosableInteger] ，因此無需通過參數傳遞?；蛘吣阆雮鬟f的話，把引用往下傳也是可以的。

?

這里的 [1, maxChoosableInteger] 指的是一個左右閉合的區(qū)間。

?

為了方便大家理解，我畫了一個邏輯樹：

接下來，我們寫代碼遍歷這棵樹即可。

「可重復選」的暴力核心代碼如下：

class?Solution:
????def?canIWin(self,?maxChoosableInteger:?int,?desiredTotal:?int)?->?bool:
????????#?acc?表示當前累計的數字和
????????def?dfs(acc):
????????????if?acc?>=?desiredTotal:
????????????????return?False
????????????for?n?in?range(1,?maxChoosableInteger?+?1):
????????????????#?對方有一種情況贏不了，我就選這個數字就能贏了，返回 true，代表可以贏。
????????????????if?not?dfs(acc?+?n):
????????????????????return?True
????????????return?False

????????#?初始化集合，用于保存當前已經選擇過的數。
????????return?dfs(0)

上面代碼已經很清晰了，并且加了注釋，我就不多解釋了。我們繼續(xù)來看下「如果數字不允許重復選」 會怎么樣？

一個直觀的思路是使用 set 記錄已經被取的數字。當選數字的時候，如果是在 set 中則不取即可。由于可選數字在「動態(tài)變化」。也就是說上面的邏輯樹部分，每個樹節(jié)點的可選數字都是不同的。

那怎么辦呢？很簡單，通過參數傳遞唄。而且：

• 要么 set 是值傳遞，這樣不會相互影響。
• 要么每次遞歸返回的是時候主動回溯狀態(tài)。關于這塊不熟悉的，可以看下我之前寫過的回溯專題^[2]。

如果使用值傳遞，對應是這樣的：

如果在每次遞歸返回的是時候主動回溯狀態(tài)，對應是這樣的：

注意圖上的藍色的新增的線，他們表示遞歸返回的過程。我們需要在返回的過程「撤銷選擇」。比如我選了數組 2， 遞歸返回的時候再把數字 2 從 set 中移除。

簡單對比下兩種方法。

• 使用 set 的值傳遞，每個遞歸樹的節(jié)點都會存一個完整的 set，空間大概是 「節(jié)點的數目」 X 「set 中數字個數」，因此空間復雜度大概是 ， 這個空間根本不可想象，太大了。

• 使用本狀態(tài)回溯的方式。由于每次都要從 set 中移除指定數字，時間復雜度是 ，這樣做時間復雜度又太高了。

這里我用了第二種方式 - 狀態(tài)回溯。和上面代碼沒有太大的區(qū)別，只是加了一個 set 而已，唯一需要注意的是需要在回溯過程恢復狀態(tài)（picked.remove(n)）。

代碼

代碼支持：Python3

Python3 Code:

class?Solution:
????def?canIWin(self,?maxChoosableInteger:?int,?desiredTotal:?int)?->?bool:
????????if?desiredTotal?<=?maxChoosableInteger:
????????????return?True
????????if?sum(range(maxChoosableInteger?+?1))?????????????return?False
????????# picked 用于保存當前已經選擇過的數。
????????#?acc?表示當前累計的數字和
????????def?backtrack(picked,?acc):
????????????if?acc?>=?desiredTotal:
????????????????return?False
????????????if?len(picked)?==?maxChoosableInteger:
????????????????#?說明全部都被選了，沒得選了，返回 False，?代表輸了。
????????????????return?False
????????????for?n?in?range(1,?maxChoosableInteger?+?1):
????????????????if?n?not?in?picked:
????????????????????picked.add(n)
????????????????????#?對方有一種情況贏不了，我就選這個數字就能贏了，返回 true，代表可以贏。
????????????????????if?not?backtrack(picked,?acc?+?n):
????????????????????????picked.remove(n)
????????????????????????return?True
????????????????????picked.remove(n)
????????????return?False

????????#?初始化集合，用于保存當前已經選擇過的數。
????????return?backtrack(set(),?0)

狀態(tài)壓縮 + 回溯

思路

有的同學可能會問， 為什么不使用記憶化遞歸？這樣可以有效減少邏輯樹的節(jié)點數，從指數級下降到多項式級。這里的原因在于 set 是不可直接序列化的，因此不可直接存儲到諸如哈希表這樣的數據結構。

而如果你自己寫序列化，比如最粗糙的將 set 轉換為字符串或者元祖存。看起來可行，set 是 ordered 的，因此如果想正確序列化還需要排序。當然你可用一個 orderedhashset，不過效率依然不好，感興趣的可以研究一下。

如下圖，兩個 set 應該一樣，但是遍歷的結果順序可能不同，如果不排序就可能有錯誤。

至此，問題的關鍵基本上鎖定為找到一個「可以序列化且容量大大減少的數據結構」來存是不是就可行了？

注意到 「maxChoosableInteger? 不會大于 20」 這是一個強有力的提示。由于 20 是一個不大于 32 的數字， 因此這道題很有可能和狀態(tài)壓縮有關，比如用 4 個字節(jié)存儲狀態(tài)。力扣相關的題目還有不少， 具體大家可參考文末的相關題目。

我們可以將狀態(tài)進行壓縮，使用位來模擬。實際上使用狀態(tài)壓縮和上面「思路一模一樣，只是 API 不一樣」罷了。

假如我們使用的這個用來代替 set 的數字名稱為 picked。

• picked 第一位表示數字 1 的使用情況。
• picked 第二位表示數字 2 的使用情況。
• picked 第三位表示數字 3 的使用情況。
• 。。。

比如我們剛才用了集合，用到的集合 api 有：

• in 操作符，判斷一個數字是否在集合中
• add(n) 函數， 用于將一個數加入到集合
• len()，用于判斷集合的大小

那我們其實就用位來模擬實現(xiàn)這三個 api 就罷了。詳細可參考我的這篇題解 - 面試題 01.01. 判定字符是否唯一 ^[3]

如果實現(xiàn) add 操作？

這個不難。比如我要模擬 picked.add(n)，只要將 picked 第 n 為置為 1 就行。也就是說 1 表示在集合中，0 表示不在。

使用「或運算和位移運算」可以很好的完成這個需求。

「位移運算」

1?<

指的是 1 的二進制表示全體左移 a 位， 右移也是同理

「| 操作」

a?|?b

指的是 a 和 b 每一位都進行或運算的結構。常見的用法是 a 和 b 其中一個當成是 seen。這樣就可以當「二值」數組和哈希表用了。比如：

seen?=?0b0000000
a?=?0b0000001
b?=?ob0000010

seen?|=?a?后，??seen?為?0b0000001
seen?|=?b?后，??seen?為?0b0000011

這樣我就可以知道 a 和 b 出現(xiàn)過了。當然 a ， b 以及其他你需要統(tǒng)計的數字只能用一位。典型的是題目只需要存 26 個字母，那么一個 int( 32 bit) 足夠了。如果是包括大寫，那就是 52， 就需要至少 52 bit。

如何實現(xiàn) in 操作符？

有了上面的鋪墊就簡單了。比如要模擬 n in picked。那只要判斷 picked 的第 n 位是 0 還是 1 就行了。如果是 0 表示不在 picked 中，如果是 1 表示在 picked 中。

用「或運算和位移運算」可以很好的完成這個需求。

「& 操作」

a?&?b

指的是 a 和 b 每一位都進行與運算的結構。常見的用法是 a 和 b 其中一個是 mask。這樣就可以得指定位是 0 還是 1 了。比如：

mask?=?0b0000010
a?&?mask?==?1?說明?a?在第二位（從低到高）是?1
a?&?mask?==?0?說明?a?在第二位（從低到高）是?0

如何實現(xiàn) len

其實只要逐個 bit 比對，如果當前 bit 是 1 則計數器 + 1，最后返回計數器的值即可。

這沒有問題。而實際上，我們只關心集合大小是否等于 maxChoosableInteger。也就是我只關心「第 maxChoosableInteger 位以及低于 maxChoosableInteger 的位是否全部是 1」。

這就簡單了，我們只需要將 1 左移 maxChoosableInteger + 1 位再減去 1 即可。一行代碼搞定：

picked?==?(1?<1))?-?1

上面代碼返回 true 表示滿了， 否則沒滿。

至此大家應該感受到了，使用位來代替 set 思路上沒有任何區(qū)別。不同的僅僅是 API 而已。如果你只會使用 set 不會使用位運算進行狀態(tài)壓縮，只能說明你對位 的 api 不熟而已。多練習幾道就行了，文末我列舉了幾道類似的題目，大家不要錯過哦~

關鍵點分析

• 回溯
• 動態(tài)規(guī)劃
• 狀態(tài)壓縮

代碼

代碼支持：Java,CPP,Python3,JS

Java Code:

public?class?Solution?{
????public?boolean?canIWin(int?maxChoosableInteger,?int?desiredTotal)?{

????????if?(maxChoosableInteger?>=?desiredTotal)?return?true;
????????if?((1?+?maxChoosableInteger)?*?maxChoosableInteger?/?2?return?false;

????????Boolean[]?dp?=?new?Boolean[(1?<1];
????????return?dfs(maxChoosableInteger,?desiredTotal,?0,?dp);
????}

????private?boolean?dfs(int?maxChoosableInteger,?int?desiredTotal,?int?state,?Boolean[]?dp)?{
????????if?(dp[state]?!=?null)
????????????return?dp[state];
????????for?(int?i?=?1;?i?<=?maxChoosableInteger;?i++){
????????????int?tmp?=?(1?<1));
????????????if?((tmp?&?state)?==?0){
????????????????if?(desiredTotal?-?i?<=?0?||?!dfs(maxChoosableInteger,?desiredTotal?-?i,?tmp|state,?dp))?{
????????????????????dp[state]?=?true;
????????????????????return?true;
????????????????}
????????????}
????????}
????????dp[state]?=?false;
????????return?false;
????}
}

C++ Code:

class?Solution?{
public:
????bool?canIWin(int?maxChoosableInteger,?int?desiredTotal)?{
????????int?sum?=?(1+maxChoosableInteger)*maxChoosableInteger/2;
????????if(sum?????????????return?false;
????????}
????????unordered_map<int,int>?d;
????????return?dfs(maxChoosableInteger,0,desiredTotal,0,d);
????}

????bool?dfs(int?n,int?s,int?t,int?S,unordered_map<int,int>&?d){
????????if(d[S])?return??d[S];
????????int&?ans?=?d[S];

????????if(s?>=?t){
????????????return?ans?=?true;
????????}
????????if(S?==?(((1?<-1)?<1)){
????????????return?ans?=?false;
????????}

????????for(int?m?=?1;m?<=n;++m){
????????????if(S?&?(1?<????????????????continue;
????????????}
????????????int?nextS?=?S|(1?<????????????if(s+m?>=?t){
????????????????return?ans?=?true;
????????????}
????????????bool?r1?=?dfs(n,s+m,t,nextS,d);
????????????if(!r1){
????????????????return?ans?=?true;
????????????}
????????}
????????return?ans?=?false;
????}
};

Python3 Code:

class?Solution:
????def?canIWin(self,?maxChoosableInteger:?int,?desiredTotal:?int)?->?bool:
????????if?desiredTotal?<=?maxChoosableInteger:
????????????return?True
????????if?sum(range(maxChoosableInteger?+?1))?????????????return?False

????????@lru_cache(None)
????????def?dp(picked,?acc):
????????????if?acc?>=?desiredTotal:
????????????????return?False
????????????if?picked?==?(1?<1))?-?1:
????????????????return?False
????????????for?n?in?range(1,?maxChoosableInteger?+?1):
????????????????if?picked?&?1?<0:
????????????????????if?not?dp(picked?|?1?<????????????????????????return?True
????????????return?False

????????return?dp(0,?0)

JS Code:

var?canIWin?=?function?(maxChoosableInteger,?desiredTotal)?{
??//?直接獲勝
??if?(maxChoosableInteger?>=?desiredTotal)?return?true;

??//?全部拿完也無法到達
??var?sum?=?(maxChoosableInteger?*?(maxChoosableInteger?+?1))?/?2;
??if?(desiredTotal?>?sum)?return?false;

??//?記憶化
??var?dp?=?{};

??/**
???*?@param?{number}?total?剩余的數量
???*?@param?{number}?state?使用二進制位表示抽過的狀態(tài)
???*/
??function?f(total,?state)?{
????//?有緩存
????if?(dp[state]?!==?undefined)?return?dp[state];

????for?(var?i?=?1;?i?<=?maxChoosableInteger;?i++)?{
??????var?curr?=?1?<??????//?已經抽過這個數
??????if?(curr?&?state)?continue;
??????//?直接獲勝
??????if?(i?>=?total)?return?(dp[state]?=?true);
??????//?可以讓對方輸
??????if?(!f(total?-?i,?state?|?curr))?return?(dp[state]?=?true);
????}

????//?沒有任何讓對方輸的方法
????return?(dp[state]?=?false);
??}

??return?f(desiredTotal,?0);
};

相關題目

• 面試題 01.01. 判定字符是否唯一 ?純狀態(tài)壓縮，無 DP
• 698. 劃分為 k 個相等的子集
• 1681. 最小不兼容性

大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：https://github.com/azl397985856/leetcode 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。

Reference