状压DP

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

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

集合操作

位运算

intersection A∩B

A & B

union A∪B

A | B

complementary Aᶜ

relative complementary A\B

A & (~B)

symmetric difference A△B

A ^ B

一些操作：

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

热身：子集(power set)

除了前面提到的用DFS求解，还可以枚举所有用整数的二进制表示来枚举nums的所有 $2^n$ 个子集(包括空集的power set)。然后在每个状态中判断是否各个数字被选中。

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

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

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

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

TSP

来看看经典的TSP（Traveling salesman problem）:

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

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

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

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

参考代码：

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])

我能赢吗

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

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

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

输入：
maxChoosableInteger = 10
desiredTotal = 11

输出：
false

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

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)

路径问题

不同路径：有顺序的放球问题

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

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

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：二维路径数（方案数）DP

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

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

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

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：状态压缩DP

在二维网格 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)

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个相等的子集

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

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

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

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

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

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)

完成所有工作的最短时间

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

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

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

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

# 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]

# 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

棋盘

N皇后

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

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

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

N国王 [SCOI2005]互不侵犯

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

参考代码：

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

Previous背包DP Next图论

Last updated 4 years ago

hashtag热身：子集arrow-up-right(power set)

hashtagTSP

hashtag我能赢吗arrow-up-right

hashtag路径问题

hashtag不同路径arrow-up-right：有顺序的放球问题

hashtag不同路径 IIarrow-up-right：二维路径数（方案数）DP

hashtag不同路径 IIIarrow-up-right：状态压缩DP

hashtag分割子集

hashtag划分为k个相等的子集arrow-up-right

hashtag完成所有工作的最短时间arrow-up-right

hashtag棋盘

hashtagN皇后arrow-up-right

hashtagN国王 [SCOI2005]互不侵犯arrow-up-right