# 状压DP

状压(state compression)DP似乎不怎么常看到，其实也并不复杂。只是在一般的用整数作为状态索引 $$f\[i]$$或者 $$f\[i]\[j]$$ 中的 $$i$$ 或者 $$j$$ 变成了用二进制作索引。这样就能方便地列举在选择问题中指数个（$$2^n$$）状态了。 

先来熟悉一下集合运算的位运算：

| 集合操作                       | 位运算       | <p></p><p></p>                                                                                                                                                                                                                                                                                     |
| -------------------------- | --------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| intersection A∩B           | A & B     | <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Venn0001.svg/220px-Venn0001.svg.png" alt="" data-size="line">                                                                                                                                                                  |
| union A∪B                  | A \| B    | <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Venn0111.svg/200px-Venn0111.svg.png" alt="" data-size="line">                                                                                                                                                                  |
| complementary Aᶜ           | \~A       | <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Venn10.svg/250px-Venn10.svg.png" alt="An unfilled circle inside a square. The area inside the square not covered by the circle is filled with red. The borders of both the circle and the square are black." data-size="line"> |
| relative complementary A\B | A & (\~B) | <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5a/Venn0010.svg/250px-Venn0010.svg.png" alt="" data-size="line">                                                                                                                                                                  |
| symmetric difference A△B   | A ^ B     | <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Venn0110.svg/220px-Venn0110.svg.png" alt="" data-size="line">                                                                                                                                                                  |

一些操作：

```python
state =| (1<<i) # 从状态state加入i
state & ~(1<<i) # 从状态state去掉i
state & (1<<i)  # 判断state是否包括i，或者写成(state>>i)&1

s &= s-1   # 最低位的 1 置成 0
p = s & -s # 获得最低位的1的位置(1&-1=1，2&-2=2）

s = state
while s:
    yield s # 遍历state的非空子集s
    s = (s-1) & state
```

## 热身：[**子集**](https://leetcode-cn.com/problems/subsets/)**(power set)**

除了前面提到的用[DFS求解](https://maomaoalgo.gitbook.io/python/suan-fa-ji-chu/shen-du-you-xian#zi-ji-pai-lie)，还可以枚举所有用整数的二进制表示来枚举nums的所有$$2^n$$个子集(包括空集的power set)。然后在每个状态中判断是否各个数字被选中。

```python
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

{% tabs %}
{% tab title="状态枚举" %}

```python
res = []
for i in range(1<<len(nums)): # 枚举子集
                                             # 判断数字是否被选中
    res.append([nums[j] for j in range(len(nums)) if (i>>j)&1])
return res
```

{% endtab %}

{% tab title="DFS" %}

```python
def dfs(path, i):
    res.append(path)
    for j in range(i, len(nums)):
        dfs(path+[nums[j]], j+1)

res = []
dfs([], 0)
return res
```

{% endtab %}
{% endtabs %}

## TSP

来看看经典的[TSP（Traveling salesman problem）](https://en.wikipedia.org/wiki/Travelling_salesman_problem):

> 给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

如果城市的数量不多的话（n<10），那么我们就可以用状压DP来求解。具体地说，我们用 $$f\[\text{pos}, \text{state}]$$ 来表示身处 $$\text{pos}$$ ，走过 $$\text{state}$$ （二进位数字）城市后最小花费。 $$f$$ 的状态数一共有 $$O(n \cdot 2^n)$$ 个。我们把起点叫做 $$s$$ ，求解过程：

1. **初始化**： $$f\[s, { s}] = 0$$ ，其余均等于 $$\inf$$&#x20;
2. **状态转移**： $$f\[j,  \text{state}+{j}] = \min\_{i \in \text{state}} (f\[i,  \text{state}] + \text{cost }\[i, j])$$ &#x20;
3. **求解**： $$\text{res} = \min\_{i} (f\[i]\[1 << n -1] + \text{cost}\[i]\[s])$$ ，等于到达城市 $$i$$且遍历了所有城市的最小花费，加上返回到起点的最小花费。

这里**用二进制来表示** $$\text{state}$$ **，再用DP实现最小花费计算**，就是状压DP的过程。

**参考代码：**

```python
f[start][1<<(start-1)] = 0
for state in range(1<<n):
    for i in range(1, n+1):
        if not state & (1<<(i-1)): continue # 选择包含i的state
        for j in range(1, n+1):
            if state & (1<<(j-1)): continue # 选择state中不存在的新j
            nstate = state|(1<<(j-1)
            f[j][nstate] = min(f[j][nstate],
                               f[i][state]+dist[i][j])

res = float('inf')
for i in range(1, n+1):
    if i==start: continue
    res = min(res, f[i][(1<<n)-1] + cost[i][start])
```

## [我能赢吗](https://leetcode-cn.com/problems/can-i-win/)

```python
两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
先使得累计整数和达到或超过 100 的玩家，即为胜者。

给定一个整数 maxChoosableInteger （整数池中可选择的最大数）
和另一个整数 desiredTotal（累计和），
判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。

输入：
maxChoosableInteger = 10
desiredTotal = 11

输出：
false

解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
```

```python
def canIWin(m, d):
    if d<=m: return True
    if sum(range(m+1)) < d: return False
    @cache
    def dfs(state, points):
        for i in range(1, m+1):
            if (state & 1<<i): continue
            if points+i >= d or \
                not dfs(state|(1<<i), points+i):
                return True
        return False
    return dfs(0, 0)
```

## 路径问题

### [不同路径](https://leetcode-cn.com/problems/unique-paths/)：有顺序的放球问题

```python
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。
机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？
```

```python
def uniquePaths(self, m: int, n: int) -> int:
    # C(m+n-2, n-1)
    return factorial(m+n-2)//factorial(n-1)//factorial(m-1)

# DP
def uniquePaths(self, m: int, n: int) -> int:
    f = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i==0 or j==0: f[i][j] = 1
            else: f[i][j] = f[i-1][j] + f[i][j-1]
    return f[-1][-1]
```

### [不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)：二维路径数（方案数）DP

```
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。
机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
```

```python
def uniquePathsWithObstacles(obstacleGrid: List[List[int]]) -> int:
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    f = [[0]*(n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if obstacleGrid[i-1][j-1]==1: continue
            elif i==j==1: f[i][j] = 1
            else: f[i][j] = f[i-1][j]+f[i][j-1]
    return f[-1][-1]
```

### [不同路径 III](https://leetcode-cn.com/problems/unique-paths-iii/)：状态压缩DP

```python
在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
```

```python
def uniquePathsIII(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    di, dj = (1, -1, 0, 0), (0, 0, 1, -1)
    def pos(i, j): return 1<<(i*n + j)
    def bound(vis, i, j):
        return 0<=i<m and 0<=j<n and not vis & pos(i, j)
    
    def dfs(vis,i,j):
        nonlocal cnt
        if grid[i][j] == 2: return +(cnt==0)
        res = 0
        for d in range(4):
            ni, nj = i+di[d], j+dj[d]
            if bound(vis, ni, nj):
                cnt-=1
                res += dfs(vis | pos(ni, nj), ni, nj)
                cnt+=1
        return res

    ti = tj = cnt = vis = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j]%2 == 0:  cnt += 1
            elif grid[i][j] == -1: vis |= pos(i, j)
            elif grid[i][j] == 1:  ti, tj = i, j
    return dfs(vis|pos(ti, tj), ti, tj)
```

## 分割子集

### [划分为k个相等的子集](https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/)

这题的解法不是DP，而需要暴力搜索所有的分割子集方法。

枚举子集在搜索过程中不会出现重复选中的元素。这里和枚举子集不一样，因为每个元素最后都要落到某一个子集，所以有可能要重头搜索见参考代码中`dfs(vis, target, 0, k-1)`。所以用二进制的“状态“来表示每个元素是否已被选，就可以避开那些已经考虑过的元素了。

```python
给定一个整数数组  nums 和一个正整数 k，
找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
```

{% tabs %}
{% tab title="状压DFS" %}

```python
def canPartitionKSubsets(nums: List[int], k: int) -> bool:
    target, rem = divmod(sum(nums), k)
    if rem or target < max(nums): return False

    def dfs(vis, t, ind, k):
        if t==0: return True if k<=1 else dfs(vis, target, 0, k-1)
        for i in range(ind, len(nums)):
            if (vis>>i)&1 or nums[i]>t: continue
            if dfs(vis|(1<<i), t-nums[i], i+1, k):
                return True
        return False

    return dfs(0, target, 0, k-1) # make k-1 cuts to get k groups
```

{% endtab %}

{% tab title="DFS+回溯" %}

```python
def canPartitionKSubsets(nums, k):
    target, rem = divmod(sum(nums), k)
    if rem or target < max(nums): return False
    nums.sort()
    while nums and nums[-1] == target:
        nums.pop()
        k -= 1
    while nums and nums[0] == 0:
        nums.pop(0)

    def search(groups):
        if not nums: return True
        v = nums.pop()
        for i, group in enumerate(groups):
            if group + v <= target:
                groups[i] += v
                if search(groups): return True
                groups[i] -= v
            if not group: break
        nums.append(v)
        return False

    return search([0] * k)
```

{% endtab %}
{% endtabs %}

### [**完成所有工作的最短时间**](https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/)

```python
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。
工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。
请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能 最小 的 最大工作时间 。

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。
```

{% tabs %}
{% tab title="状压DP" %}

```python
# similar to
# https://leetcode-cn.com/problems/
# distribute-repeating-integers/
def minimumTimeRequiredDP(jobs, k):
    n = len(jobs)
    tot = [0 for _ in range(1<<n)]
    for i in range(1, 1<<n):
        for j in range(n):
            if i & (1<<j)==0: continue
            left = i - (1<<j)
            tot[i] = tot[left] + jobs[j]
            break
    
    f = [[-1]*(1<<n) for _ in range(k)]
    for i in range(1<<n):
        f[0][i] = tot[i]
    
    for j in range(1, k):
        for i in range(1<<n):
            minv = float('inf')
            s = i
            while s:
                left = i-s
                val = max(f[j-1][left], tot[s])
                minv = min(minv, val)
                s = (s-1) & i
            f[j][i] = minv
    return f[k-1][(1<<n)-1]
```

{% endtab %}

{% tab title="DFS+回溯" %}

```python
# similar to
# https://leetcode-cn.com/problems/
# partition-to-k-equal-sum-subsets/
def minimumTimeRequired(job, k):
    def canFinish(nums, groups, target):
        if not nums: return True
        v = nums.pop()
        for i in range(len(groups)):
            if groups[i] + v > target: continue
            groups[i] += v
            if canFinish(nums, groups, target):
                return True
            groups[i] -= v # backtrack job assignment
            if groups[i] == 0: break # PRUNING!
        nums.append(v) # backtrack assigning job
        return False

    def can(target):
        nums = sorted(jobs) # PRUNING
        groups = [0 for _ in range(k)]
        return canFinish(nums, groups, target)

    l, r = max(jobs), sum(jobs)
    while l<=r:
        m = (l+r) >> 1
        if can(m):
            r = m-1
        else:
            l = m+1
    return l
```

{% endtab %}
{% endtabs %}

## 棋盘

### [N皇后](https://leetcode-cn.com/problems/n-queens-ii/)

如何将N个皇后放置在NxN的棋盘上，并且使皇后彼此之间不能相互攻击，共有多少种摆放方案。皇后能攻击到它上下左右，以及左上左下右上右下八个方向上任意一个格子。

{% tabs %}
{% tab title="状压DFS" %}

```python
def totalNQueens():
    def dfs(row, col, ld, rd):
        nonlocal res
        if row==n:
            res += 1
            return
        mask = ~(col | ld | rd) & ((1<<n) - 1)
        while mask:
            pick = mask & -mask # 获得最低位的1的位置
            dfs(row+1, col|pick, (ld|pick)<<1, (rd|pick)>>1)
            mask &= mask-1 # 最低位的 1 置成 0
    res = 0
    state = 0
    dfs(0, 0, 0, 0)
    return res
```

{% endtab %}

{% tab title="DFS+回溯" %}

```python
def totalNQueens(n):
    def validQueen(i, j):
        if not 0<=i<n or not 0<=j<n:
            return False
        for k in range(i): # left, and up
            if board[i][k]=="Q" or board[k][j]=="Q":
                return False
        x, y = i-1, j+1
        while x>=0 and y<n:
            if board[x][y]=="Q":
                return False
            x -= 1
            y += 1
        x, y = i-1, j-1
        while x>=0 and y>=0:
            if board[x][y]=="Q":
                return False
            x -= 1
            y -= 1
        return True
    
    def dfs(row):
        nonlocal res
        if row==n:
            res += 1
            return
        for col in range(n):
            if validQueen(row, col):
                board[row][col] = "Q"
                dfs(row+1)
                board[row][col] = "."
    
    res = 0
    board = [["."]*n for _ in range(n)]
    dfs(0)
    return res
```

{% endtab %}
{% endtabs %}

### N国王 [\[SCOI2005\]互不侵犯](https://www.luogu.com.cn/problem/P1896)

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

**参考代码：**

```python
def NKings(n, k):
    def dfs(x, num, cur):
        nonlocal cnt
        if cur >= n:
            cnt += 1
            sit[cnt] = x
            sta[cnt] = num
            return
        dfs(x, num, cur+1)
        dfs(x | (1<<cur), num+1, cur+2)
    
    def status(x):
        return str(bin(x))[2:].zfill(5)
        
    def compatible(j, x):
        if sit[j] & sit[x]: return False
        if ((sit[j]<<1) & sit[x]): return False
        if (sit[j] & (sit[x]<<1)): return False
        return True
    
    cnt = 0
    nking = 1000
    f = [[[0]*105 for _ in range(nking)] for _ in range(15)]
    # f[i][j][l]
    # i: number of rows used
    # j: status index, total of cnt status
    # l: number of kings used
    sit = [0 for _ in range(nking)]
    sta = [0 for _ in range(nking)]
    dfs(0, 0, 0)
    for j in range(1, cnt+1):
        f[1][j][sta[j]] = 1
    
    for i in range(2, n+1):
        for j in range(1, cnt+1):
            for x in range(1, cnt+1):
                if not compatible(j, x): continue
                for l in range(sta[j], k+1):
                    f[i][j][l] += f[i-1][x][l-sta[j]]
    
    res = 0
    for i in range(1, cnt+1):
        res += f[n][i][k]
    return res
```