关于动态规划:状压-DP-是什么这篇题解带你入门

题目地址（464. 我能赢么）

https://leetcode-cn.com/probl...

题目形容

在 "100 game" 这个游戏中，两名玩家轮流抉择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过 100 的玩家，即为胜者。如果咱们将游戏规则改为 “玩家不能重复使用整数” 呢？例如，两个玩家能够轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。给定一个整数 maxChoosableInteger （整数池中可抉择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假如两位玩家游戏时都体现最佳）？你能够假如 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。示例：输出：maxChoosableInteger = 10desiredTotal = 11输入：false解释：无论第一个玩家抉择哪个整数，他都会失败。第一个玩家能够抉择从 1 到 10 的整数。如果第一个玩家抉择 1，那么第二个玩家只能抉择从 2 到 10 的整数。第二个玩家能够通过抉择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.同样地，第一个玩家抉择任意其余整数，第二个玩家都会赢。

前置常识

动静布局
回溯

公司

阿里
linkedin

暴力解（超时）

思路

题目的函数签名如下：

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

即给你两个整数 maxChoosableInteger 和 desiredTotal，让你返回一个布尔值。

两种非凡状况

首先思考两种非凡状况，前面所有的解法这两种非凡状况都实用，因而不再赘述。

如果 desiredTotal 是小于等于 maxChoosableInteger 的，间接返回 True，这不难理解。
如果 [1, maxChoosableInteger] 全副数字之和小于 desiredTotal，谁都无奈赢，返回 False。

个别状况

思考完了非凡状况，咱们持续思考个别状况。

首先咱们来简化一下问题，如果数字能够轻易选呢？这个问题就简略多了，和爬楼梯没啥区别。这里思考暴力求解，应用 DFS + 模仿的形式来解决。

留神到每次可选的数字都不变，都是 [1, maxChoosableInteger] ，因而无需通过参数传递。或者你想传递的话，把援用往下传也是能够的。

这里的 [1, maxChoosableInteger] 指的是一个左右闭合的区间。

为了不便大家了解，我画了一个逻辑树：

接下来，咱们写代码遍历这棵树即可。

可反复选的暴力外围代码如下：

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 backtrack(acc + n):                    return True            return False        # 初始化汇合，用于保留以后曾经抉择过的数。        return dfs(0)

下面代码曾经很清晰了，并且加了正文，我就不多解释了。咱们持续来看下如果数字不容许反复选 会怎么样？

一个直观的思路是应用 set 记录曾经被取的数字。入选数字的时候，如果是在 set 中则不取即可。因为可选数字在动态变化。也就是说下面的逻辑树局部，每个树节点的可选数字都是不同的。

那怎么办呢？很简略，通过参数传递呗。而且：

要么 set 是值传递，这样不会相互影响。
要么每次递归返回的是时候被动回溯状态。对于这块不相熟的，能够看下我之前写过的回溯专题。

如果应用值传递，对应是这样的：

如果在每次递归返回的是时候被动回溯状态，对应是这样的：

留神图上的蓝色的新增的线，他们示意递归返回的过程。咱们须要在返回的过程撤销抉择。比方我选了数组 2，递归返回的时候再把数字 2 从 set 中移除。

简略比照下两种办法。

应用 set 的值传递，每个递归树的节点都会存一个残缺的 set，空间大略是 节点的数目 X set 中数字个数，因而空间复杂度大略是 $O(2^maxChoosableInteger * maxChoosableInteger)$，这个空间基本不可设想，太大了。
应用本状态回溯的形式。因为每次都要从 set 中移除指定数字，工夫复杂度是 $O(maxChoosableInteger X 节点数)$，这样做工夫复杂度又太高了。

这里我用了第二种形式 - 状态回溯。和下面代码没有太大的区别，只是加了一个 set 而已，惟一须要留神的是须要在回溯过程复原状态（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)) < desiredTotal:            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)

状态压缩 + 回溯

思路

有的同学可能会问，为什么不应用记忆化递归？这样能够无效缩小逻辑树的节点数，从指数级降落到多项式级。这里的起因在于 set 是不可间接序列化的，因而不可间接存储到诸如哈希表这样的数据结构。

而如果你本人写序列化，比方最毛糙的将 set 转换为字符串或者元祖存。看起来可行，set 是 ordered 的，因而如果想正确序列化还须要排序。当然你可用一个 orderedhashset，不过效率仍然不好，感兴趣的能够钻研一下。

如下图，两个 set 应该一样，然而遍历的后果程序可能不同，如果不排序就可能有谬误。

至此，问题的要害基本上锁定为找到一个能够序列化且容量大大减少的数据结构来存是不是就可行了？

留神到 maxChoosableInteger 不会大于 20 这是一个强有力的提醒。因为 20 是一个不大于 32 的数字，因而这道题很有可能和状态压缩无关，比方用 4 个字节存储状态。力扣相干的题目还有不少，具体大家可参考文末的相干题目。

咱们能够将状态进行压缩，应用位来模仿。实际上应用状态压缩和下面思路截然不同，只是 API 不一样罢了。

如果咱们应用的这个用来代替 set 的数字名称为 picked。

picked 第一位示意数字 1 的应用状况。
picked 第二位示意数字 2 的应用状况。
picked 第三位示意数字 3 的应用状况。
。。。

比方咱们方才用了汇合，用到的汇合 api 有：

in 操作符，判断一个数字是否在汇合中
add(n) 函数，用于将一个数退出到汇合
len()，用于判断汇合的大小

那咱们其实就用位来模仿实现这三个 api 就罢了。具体可参考我的这篇题解 - 面试题 01.01. 断定字符是否惟一

如果实现 add 操作？

这个不难。比方我要模仿 picked.add(n)，只有将 picked 第 n 为置为 1 就行。也就是说 1 示意在汇合中，0 示意不在。

应用或运算和位移运算能够很好的实现这个需要。

位移运算

1 << a

指的是 1 的二进制示意整体左移 a 位，右移也是同理

| 操作

a | b

指的是 a 和 b 每一位都进行或运算的构造。常见的用法是 a 和 b 其中一个当成是 seen。这样就能够当二值数组和哈希表用了。比方：

seen = 0b0000000a = 0b0000001b = ob0000010seen |= a 后，  seen 为 0b0000001seen |= b 后，  seen 为 0b0000011

这样我就能够晓得 a 和 b 呈现过了。当然 a ， b 以及其余你须要统计的数字只能用一位。典型的是题目只须要存 26 个字母，那么一个 int( 32 bit) 足够了。如果是包含大写，那就是 52，就须要至多 52 bit。

如何实现 in 操作符？

有了下面的铺垫就简略了。比方要模仿 n in picked。那只有判断 picked 的第 n 位是 0 还是 1 就行了。如果是 0 示意不在 picked 中，如果是 1 示意在 picked 中。

用或运算和位移运算能够很好的实现这个需要。

& 操作

a & b

指的是 a 和 b 每一位都进行与运算的构造。常见的用法是 a 和 b 其中一个是 mask。这样就能够得指定位是 0 还是 1 了。比方：

mask = 0b0000010a & mask == 1 阐明 a 在第二位（从低到高）是 1a & mask == 0 阐明 a 在第二位（从低到高）是 0

如何实现 len

其实只有一一 bit 比对，如果以后 bit 是 1 则计数器 + 1，最初返回计数器的值即可。

这没有问题。而实际上，咱们只关怀汇合大小是否等于 maxChoosableInteger。也就是我只关怀第 maxChoosableInteger 位以及低于 maxChoosableInteger 的位是否全副是 1。

这就简略了，咱们只须要将 1 左移 maxChoosableInteger + 1 位再减去 1 即可。一行代码搞定：

picked == (1 << (maxChoosableInteger + 1)) - 1

下面代码返回 true 示意满了，否则没满。

至此大家应该感触到了，应用位来代替 set 思路上没有任何区别。不同的仅仅是 API 而已。如果你只会应用 set 不会应用位运算进行状态压缩，只能阐明你对位的 api 不熟而已。多练习几道就行了，文末我列举了几道相似的题目，大家不要错过哦~

关键点剖析

回溯
动静布局
状态压缩

代码

代码反对：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 < desiredTotal) return false;        Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 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 << (i - 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 < desiredTotal){            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 << n)-1) << 1)){            return ans = false;        }        for(int m = 1;m <=n;++m){            if(S & (1 << m)){                continue;            }            int nextS = S|(1 << m);            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)) < desiredTotal:            return False        @lru_cache(None)        def dp(picked, acc):            if acc >= desiredTotal:                return False            if picked == (1 << (maxChoosableInteger + 1)) - 1:                return False            for n in range(1, maxChoosableInteger + 1):                if picked & 1 << n == 0:                    if not dp(picked | 1 << n, acc + n):                        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 应用二进制位示意抽过的状态   */  function f(total, state) {    // 有缓存    if (dp[state] !== undefined) return dp[state];    for (var i = 1; i <= maxChoosableInteger; i++) {      var curr = 1 << i;      // 曾经抽过这个数      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. 断定字符是否惟一纯状态压缩，无 DP
698. 划分为 k 个相等的子集
1681. 最小不兼容性

大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858... 。目前曾经 37K star 啦。
大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。