一、状态压缩基础概念
1. 什么是状态压缩？
python
复制
下载
# 普通DP vs 状态压缩DP # 常规DP: dp[i][state1][state2]... 维度高，空间大 # 状态压缩: 使用位运算将多维状态压缩到一维 # 示例：旅行商问题(TSP) # 未压缩: dp[i][mask] - i当前城市，mask访问过的城市集合 # 压缩后: dp[mask<<5 | i] - 将i(0-31)压缩到mask的低5位
2. 状态表示方法
python
复制
下载
# 1. 二进制位压缩 (最常用) # 每个状态用二进制位表示，1表示选中/存在，0表示未选中/不存在 state = 0b1011 # 表示选中了第0、1、3个元素 # 2. 三进制状态压缩 # 0: 未选，1: 选中A，2: 选中B state = ternary_to_int([1, 0, 2, 1]) # 表示状态[1,0,2,1] # 3. 四进制及以上 # 用于更多状态的场景
二、位运算技巧
1. 基本位操作
python
复制
下载
class BitmaskDP: """位运算基础操作""" @staticmethod def basics(): # 1. 设置第i位为1 def set_bit(state, i): return state | (1 << i) # 2. 清除第i位（设为0） def clear_bit(state, i): return state & ~(1 << i) # 3. 切换第i位（取反） def toggle_bit(state, i): return state ^ (1 << i) # 4. 检查第i位是否为1 def check_bit(state, i): return (state >> i) & 1 # 5. 获取最低位的1的位置 def lowbit(state): return state & (-state) # 6. 移除最低位的1 def remove_lowbit(state): return state & (state - 1) # 7. 统计1的个数（popcount） def count_bits(state): cnt = 0 while state: state &= state - 1 cnt += 1 return cnt # Python内置: bin(state).count('1') # 8. 获取所有子集 def get_subsets(mask): subsets = [] sub = mask while sub: subsets.append(sub) sub = (sub - 1) & mask subsets.append(0) # 包含空集 return subsets # 9. 枚举所有长度为n的mask for mask in range(1 << n): # 0 到 2^n - 1 # 处理每个mask pass return locals()2. 高效位运算算法
python
复制
下载
# 使用内置函数优化（Python） import sys class FastBitOps: """高效位运算实现""" # 预计算popcount POPCOUNT = [0] * (1 << 16) for i in range(1 << 16): POPCOUNT[i] = POPCOUNT[i >> 1] + (i & 1) @staticmethod def fast_popcount(x): """快速计算32位整数中1的个数""" return (FastBitOps.POPCOUNT[x & 0xFFFF] + FastBitOps.POPCOUNT[(x >> 16) & 0xFFFF]) @staticmethod def next_permutation(mask): """获取相同1的个数的下一个排列（Gosper's Hack）""" # 例如：00111 -> 01011 -> 01101 -> ... c = mask & -mask r = mask + c return (((r ^ mask) >> 2) // c) | r @staticmethod def enumerate_k_bits(n, k): """枚举所有恰好有k个1的n位掩码""" mask = (1 << k) - 1 # 初始：最低k位为1 while mask < (1 << n): yield mask mask = FastBitOps.next_permutation(mask) @staticmethod def bit_parallel_dp(n, m): """位并行DP优化示例""" # 使用bitset加速状态转移 dp = [0] * (1 << n) dp[0] = 1 for i in range(m): new_dp = [0] * (1 << n) for mask in range(1 << n): if not dp[mask]: continue # 并行处理所有可能的下一位 available = ((1 << n) - 1) ^ mask sub = available while sub: new_mask = mask | sub new_dp[new_mask] += dp[mask] sub = (sub - 1) & available dp = new_dp return dp
篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
三、经典问题状态压缩
1. 旅行商问题 (TSP)
python
复制
下载
class TSP: """旅行商问题 - 状态压缩经典""" def tsp_naive(self, graph): """朴素DP: O(n²·2ⁿ)""" n = len(graph) INF = float('inf') # dp[mask][i]: 访问过mask中的城市，当前在i的最小花费 dp = [[INF] * n for _ in range(1 << n)] dp[1][0] = 0 # 从城市0出发 for mask in range(1 << n): for i in range(n): if not (mask >> i) & 1: continue # 从未访问过的城市j转移到i for j in range(n): if (mask >> j) & 1: continue new_mask = mask | (1 << j) dp[new_mask][j] = min( dp[new_mask][j], dp[mask][i] + graph[i][j] ) # 返回起点并形成环 res = INF final_mask = (1 << n) - 1 for i in range(1, n): res = min(res, dp[final_mask][i] + graph[i][0]) return res def tsp_optimized(self, graph): """优化版: 交换维度 + 滚动数组""" n = len(graph) INF = float('inf') # 技巧1: 交换维度，dp[i][mask] -> dp[mask][i] # 但Python中保持原顺序，使用cache友好访问 # 技巧2: 预处理每个mask的popcount popcount = [0] * (1 << n) for mask in range(1 << n): popcount[mask] = popcount[mask >> 1] + (mask & 1) # 技巧3: 按popcount分组处理 dp = [[INF] * n for _ in range(1 << n)] dp[1][0] = 0 # 按城市数量递增处理 for cnt in range(1, n + 1): # 处理所有恰好有cnt个1的mask for mask in range(1 << n): if popcount[mask] != cnt: continue # 优化内层循环 for i in range(n): if dp[mask][i] == INF: continue # 使用lowbit枚举可访问的城市 not_visited = ((1 << n) - 1) ^ mask city = not_visited while city: j = (city & -city).bit_length() - 1 new_mask = mask | (1 << j) dp[new_mask][j] = min( dp[new_mask][j], dp[mask][i] + graph[i][j] ) city &= city - 1 # 结果计算 res = INF final_mask = (1 << n) - 1 for i in range(1, n): if dp[final_mask][i] + graph[i][0] < res: res = dp[final_mask][i] + graph[i][0] return res2. 状态压缩背包问题
python
复制
下载
class KnapsackBitmask: """状态压缩解决子集背包问题""" def subset_knapsack(self, weights, values, capacity): """子集和问题：选择物品使得总重量恰好为capacity""" n = len(weights) # dp[mask] = (weight_sum, value_sum) dp = {0: (0, 0)} for mask in range(1 << n): if mask not in dp: continue w_sum, v_sum = dp[mask] # 添加新物品 for i in range(n): if (mask >> i) & 1: continue # 已选过 new_mask = mask | (1 << i) new_w = w_sum + weights[i] new_v = v_sum + values[i] if new_w <= capacity: if new_mask not in dp or new_v > dp[new_mask][1]: dp[new_mask] = (new_w, new_v) # 找最大值 max_value = 0 for w_sum, v_sum in dp.values(): if w_sum == capacity: max_value = max(max_value, v_sum) return max_value def optimized_subset_sum(self, nums, target): """优化子集和：使用bitset加速""" # 技巧：bitset表示可达的和 bitset = 1 # 第0位为1，表示和为0可达 for num in nums: # 左移num位并或运算 bitset |= (bitset << num) # 剪枝：只关心<=target的位 bitset &= (1 << (target + 1)) - 1 # 检查target是否可达 return (bitset >> target) & 1四、状态压缩优化技巧
1. 滚动数组优化
python
复制
下载
class RollingArray: """滚动数组减少空间复杂度""" def dp_with_rolling(self, n, m): """2D DP -> 滚动数组""" # 原始：dp[i][j] = dp[i-1][j] + dp[i][j-1] # 空间：O(n*m) # 优化：只保留两行 dp_prev = [0] * (m + 1) dp_curr = [0] * (m + 1) for i in range(1, n + 1): dp_curr[0] = 1 # 边界条件 for j in range(1, m + 1): dp_curr[j] = dp_prev[j] + dp_curr[j-1] # 滚动 dp_prev, dp_curr = dp_curr, [0] * (m + 1) return dp_prev[m] def space_optimized_knapsack(self, weights, values, capacity): """01背包空间优化""" n = len(weights) # 常规：dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v) # 优化：倒序更新一维数组 dp = [0] * (capacity + 1) for i in range(n): w, v = weights[i], values[i] # 必须倒序，避免重复选取 for c in range(capacity, w - 1, -1): dp[c] = max(dp[c], dp[c - w] + v) return dp[capacity]
2. 状态剪枝与预处理
python
复制
下载
class StatePruning: """状态剪枝技巧""" def valid_state_preprocessing(self, n, constraints): """预处理合法状态""" valid_states = [] # 生成所有状态并过滤 for mask in range(1 << n): if self.is_valid(mask, constraints): valid_states.append(mask) # 预计算状态转移 transitions = {} for s1 in valid_states: transitions[s1] = [] for s2 in valid_states: if self.can_transition(s1, s2): transitions[s1].append(s2) return valid_states, transitions def symmetry_reduction(self, n): """利用对称性减少状态数""" # 例如：棋盘问题中旋转/翻转对称 visited = set() representatives = [] for mask in range(1 << n): # 生成对称状态 symmetries = self.get_symmetries(mask, n) # 选择最小/最大的作为代表 rep = min(symmetries) if rep not in visited: visited.add(rep) representatives.append(rep) return representatives def prune_by_bounds(self, dp_state, lower_bound, upper_bound): """根据上下界剪枝""" if dp_state < lower_bound or dp_state > upper_bound: return None # 剪枝 # 使用启发式评估函数 estimated_cost = self.heuristic(dp_state) if estimated_cost > current_best: return None # 剪枝 return dp_state3. 记忆化搜索 + 状态压缩
python
复制
下载
from functools import lru_cache class MemoizationDP: """记忆化搜索实现状态压缩DP""" def solve_with_memo(self, graph): """记忆化搜索解决TSP""" n = len(graph) INF = float('inf') ALL = (1 << n) - 1 @lru_cache(maxsize=None) def dfs(mask, pos): """返回从pos出发，访问剩余mask中的城市的最小代价""" if mask == ALL: return graph[pos][0] # 返回起点 res = INF # 枚举下一个城市 for nxt in range(n): if (mask >> nxt) & 1: continue cost = graph[pos][nxt] + dfs(mask | (1 << nxt), nxt) res = min(res, cost) return res # 从城市0出发，已访问城市0 return dfs(1, 0) def optimized_memo(self, n, edges): """优化记忆化搜索""" # 预计算邻接矩阵/列表 adj = [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) # 使用字典缓存，比lru_cache更灵活 memo = {} def dfs(mask, u, visited_count): # 状态压缩：将(mask, u)编码为整数 state = (mask << 5) | u if state in memo: return memo[state] # 剪枝：如果已访问所有城市 if visited_count == n: return 0 res = float('inf') for v, w in adj[u]: if (mask >> v) & 1: continue res = min(res, w + dfs(mask | (1 << v), v, visited_count + 1)) memo[state] = res return res return dfs(1, 0, 1)篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
五、高级优化技巧
1. Meet in the Middle (折半搜索)
python
复制
下载
class MeetInTheMiddle: """折半搜索处理大规模状态空间""" def subset_sum_mitm(self, nums, target): """折半搜索解决子集和问题""" n = len(nums) mid = n // 2 # 前半部分所有子集的和 left_sums = [] for mask in range(1 << mid): s = sum(nums[i] for i in range(mid) if (mask >> i) & 1) left_sums.append(s) # 后半部分所有子集的和 right_sums = [] for mask in range(1 << (n - mid)): s = sum(nums[mid + i] for i in range(n - mid) if (mask >> i) & 1) right_sums.append(s) # 排序后半部分用于二分查找 right_sums.sort() # 查找匹配的组合 for left in left_sums: need = target - left # 在right_sums中二分查找need idx = bisect_left(right_sums, need) if idx < len(right_sums) and right_sums[idx] == need: return True return False def tsp_mitm(self, graph): """折半搜索优化TSP""" n = len(graph) if n <= 2: return sum(graph[0]) mid = n // 2 # 预处理两部分内部的最短路径 left_dp = self.precompute_half(graph, 0, mid) right_dp = self.precompute_half(graph, mid, n) # 合并结果 res = float('inf') for mask1 in range(1 << mid): for mask2 in range(1 << (n - mid)): # 确保所有城市都被访问 if bin(mask1).count('1') + bin(mask2).count('1') != n: continue # 计算连接两部分的代价 cost = self.connect_cost(graph, mask1, mask2, mid) total = left_dp[mask1] + right_dp[mask2] + cost res = min(res, total) return res2. 轮廓线DP (插头DP)
python
复制
下载
class ContourDP: """轮廓线DP处理棋盘类问题""" def domino_tiling(self, n, m): """多米诺骨牌覆盖问题""" # dp[state]: state是当前轮廓线的状态 # 每个位置：0表示空，1表示被覆盖 dp_prev = {0: 1} # 初始状态：全空 for i in range(n): for j in range(m): dp_curr = {} for state, count in dp_prev.items(): # 获取当前位置的状态 bit_pos = m - j - 1 # 轮廓线中的位置 curr_bit = (state >> bit_pos) & 1 if curr_bit == 1: # 当前位置已被覆盖，跳过 new_state = state & ~(1 << bit_pos) dp_curr[new_state] = dp_curr.get(new_state, 0) + count else: # 尝试横放 if j < m - 1 and ((state >> (bit_pos - 1)) & 1) == 0: new_state = state | (1 << (bit_pos - 1)) dp_curr[new_state] = dp_curr.get(new_state, 0) + count # 尝试竖放 if i < n - 1: new_state = state | (1 << bit_pos) dp_curr[new_state] = dp_curr.get(new_state, 0) + count dp_prev = dp_curr # 最终状态应为全0 return dp_prev.get(0, 0)3. 状态重编码与哈希优化
python
复制
下载
class StateEncoding: """状态重编码减少状态数""" def encode_state(self, arr): """将数组状态编码为整数""" # 方法1: 基数转换（用于多状态） result = 0 base = 1 for x in arr: result += x * base base *= 3 # 三进制编码 # 方法2: 字符串哈希 state_str = ','.join(map(str, arr)) return hash(state_str) def canonical_form(self, state, n): """获取状态的规范形式（消除对称性）""" # 生成所有旋转/翻转 forms = [] for rotation in range(4): for flip in [False, True]: transformed = self.transform(state, n, rotation, flip) forms.append(transformed) return min(forms) # 最小形式作为规范 def compress_state_dp(self, dp_states): """压缩DP状态字典""" # 使用差值编码 sorted_states = sorted(dp_states.keys()) compressed = {} prev = 0 for state in sorted_states: delta = state - prev compressed[delta] = dp_states[state] prev = state return compressed六、实战案例分析
案例1：LeetCode 1349 - 学生出勤记录
python
复制
下载
class MaxStudents: """考场座位安排问题""" def maxStudents(self, seats): m, n = len(seats), len(seats[0]) # 预处理每行的合法状态 valid_states = [] for mask in range(1 << n): # 检查是否没有相邻的1，且座位可用 if not (mask & (mask << 1)): # 没有相邻 valid_states.append(mask) # dp[i][mask]: 前i行，第i行状态为mask的最大学生数 dp = [[-1] * (1 << n) for _ in range(m + 1)] dp[0][0] = 0 for i in range(1, m + 1): row_mask = 0 for j in range(n): if seats[i-1][j] == '#': row_mask |= (1 << j) for curr in valid_states: if curr & row_mask: # 不能坐在坏椅子上 continue for prev in valid_states: if dp[i-1][prev] == -1: continue # 检查对角线冲突 if (curr & (prev >> 1)) or (curr & (prev << 1)): continue dp[i][curr] = max(dp[i][curr], dp[i-1][prev] + bin(curr).count('1')) return max(dp[m])篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
案例2：优化版数位DP
python
复制
下载
class DigitDPOptimized: """优化数位DP""" def countSpecialNumbers(self, n): """统计没有重复数字的数的个数""" s = str(n) @lru_cache(None) def dfs(pos, mask, is_limit, is_num): """记忆化搜索""" if pos == len(s): return int(is_num) res = 0 if not is_num: # 可以跳过当前位 res += dfs(pos + 1, mask, False, False) # 确定枚举上限 up = int(s[pos]) if is_limit else 9 start = 0 if is_num else 1 for d in range(start, up + 1): if (mask >> d) & 1: continue # 数字重复 res += dfs(pos + 1, mask | (1 << d), is_limit and d == up, True) return res return dfs(0, 0, True, False) def optimized_version(self, n): """优化版：预处理+状态压缩""" s = str(n) length = len(s) # 预处理组合数 C = [[0] * 10 for _ in range(10)] for i in range(10): C[i][0] = C[i][i] = 1 for j in range(1, i): C[i][j] = C[i-1][j-1] + C[i-1][j] # 计算小于len位的所有情况 total = 0 for i in range(1, length): total += 9 * self.permutation_count(9, i - 1) # 处理长度为len位的情况 mask = 0 for i in range(length): start = 1 if i == 0 else 0 digit = int(s[i]) for d in range(start, digit): if (mask >> d) & 1: continue remaining = 10 - bin(mask).count('1') - 1 positions = length - i - 1 total += self.permutation_count(remaining, positions) if (mask >> digit) & 1: break # 出现重复数字，结束 mask |= (1 << digit) if i == length - 1: total += 1 return total def permutation_count(self, n, k): """排列数 P(n, k) = n! / (n-k)!""" res = 1 for i in range(k): res *= (n - i) return res七、面试回答要点
问题：请解释动态规划的状态压缩优化
回答结构：
基本概念
"状态压缩是用位运算等技巧将多维状态压缩到一维的方法"
"核心思想：用二进制位表示状态，1表示选中/存在，0表示未选中/不存在"
常用技巧
位运算基础：
python
复制 下载# 设置/清除/检查位，枚举子集，统计1的个数
滚动数组："只保留必要的状态，减少空间复杂度"
记忆化搜索："用@lru_cache自动处理状态缓存"
经典问题应用
TSP问题："O(n²·2ⁿ) → 使用mask表示已访问城市"
棋盘覆盖："轮廓线DP，按行处理状态转移"
子集和问题："bitset优化，可达性判断"
高级优化
Meet in Middle："将问题分成两半，分别求解后合并"
状态剪枝："根据对称性、上下界减少状态数"
预处理合法状态："提前计算可能的状态转移"
实战经验
"LeetCode 1349用状态压缩解决考场座位问题"
"注意Python中1<<20大约100万状态是可行的"
"合理使用缓存和剪枝是关键"
面试技巧
举例说明：用TSP问题演示状态压缩
画图辅助：画出状态转移图
复杂度分析：说明压缩前后的复杂度对比
代码简洁：展示关键代码片段
联系实际：说明在真实系统中的应用场景
示例回答：
"在解决旅行商问题时，我们使用二进制掩码mask表示已访问的城市集合。例如mask=1011表示访问了城市0、1、3。通过位运算，我们可以高效地检查城市是否访问过，并枚举下一个城市。结合记忆化搜索，将时间复杂度从O(n!)优化到O(n²·2ⁿ)，空间复杂度从O(n!)优化到O(n·2ⁿ)。在实际编码中，我们还会使用滚动数组、状态剪枝等技巧进一步优化。"
掌握这些技巧，你就能在面试中自信地回答状态压缩DP相关的问题了！
