京东Java面试被问：动态规划的状态压缩和优化技巧-编程实验室

一、什么是状态压缩动态规划

状态压缩DP是用二进制位或位运算来表示和存储状态的一类DP，主要用于解决状态维度高但每个维度状态数少的问题（通常是布尔值）。

典型特征：

状态中的每一维只有少量可能值（通常是0/1）
状态空间巨大但可压缩
常与排列、选择、覆盖等问题相关

二、状态压缩的核心技巧

1.二进制位表示法

python

复制

下载

# 用整数mask的二进制位表示选择状态 mask = 0b10101 # 表示第0、2、4个元素被选中 n = 5 for i in range(n): if mask & (1 << i): # 检查第i位是否为1 print(f"元素{i}被选中")

2.常见位运算操作

python

复制

下载

# 基本操作 S = (1 << n) - 1 # n位全1 S & (1 << i) # 判断第i位是否为1 S | (1 << i) # 设置第i位为1 S & ~(1 << i) # 设置第i位为0 S ^ (1 << i) # 翻转第i位 S & (S - 1) # 清除最低位的1

三、经典问题模型

1.旅行商问题（TSP）

python

复制

下载

def tsp(n, dist): # dp[mask][i]: 访问过mask中的城市，最后在i城市的最小代价 dp = [[float('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 & (1 << i)): continue for j in range(n): if mask & (1 << j): continue new_mask = mask | (1 << j) dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j]) # 返回起点并形成环路 return min(dp[(1 << n) - 1][i] + dist[i][0] for i in range(1, n))

2.棋盘覆盖问题

python

复制

下载

def domino_cover(n, m): # dp[i][mask]: 处理到第i行，当前行状态为mask dp = [0] * (1 << m) dp[(1 << m) - 1] = 1 # 初始状态 for i in range(n): new_dp = [0] * (1 << m) for mask in range(1 << m): if dp[mask] == 0: continue # 递归填充当前行 def dfs(col, current_mask, next_mask): if col == m: new_dp[next_mask] += dp[mask] return # 如果当前位置已被覆盖 if mask & (1 << col): dfs(col + 1, current_mask, next_mask) else: # 竖放 if i < n - 1: dfs(col + 1, current_mask | (1 << col), next_mask | (1 << col)) # 横放 if col < m - 1 and not (mask & (1 << (col + 1))): dfs(col + 2, current_mask | (3 << col), next_mask) dfs(0, 0, 0) dp = new_dp return dp[(1 << m) - 1]

篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】

四、高级优化技巧

1.枚举子集优化

python

复制

下载

# 高效枚举mask的所有子集 def enumerate_subsets(mask): subset = mask while subset: # 处理子集subset process(subset) subset = (subset - 1) & mask # 处理空集 process(0) # 复杂度：O(3^n) 而非 O(4^n) for mask in range(1 << n): subset = mask while subset: # subset是mask的子集 complement = mask ^ subset # mask除去subset的部分 subset = (subset - 1) & mask

2.滚动数组优化

python

复制

下载

# 二维降一维 dp = [0] * (1 << n) dp[0] = 1 for i in range(m): new_dp = [0] * (1 << n) for mask in range(1 << n): if dp[mask]: # 状态转移 for new_mask in next_masks(mask): new_dp[new_mask] += dp[mask] dp = new_dp

3.预处理合法状态

python

复制

下载

# 预处理所有合法状态，减少无效转移 def preprocess_states(n): valid_states = [] for mask in range(1 << n): # 检查是否没有相邻的1 if not (mask & (mask << 1)): valid_states.append(mask) return valid_states # 预处理状态间转移 def preprocess_transitions(valid_states): transitions = {} for s1 in valid_states: transitions[s1] = [] for s2 in valid_states: if not (s1 & s2): # 状态兼容性检查 transitions[s1].append(s2) return transitions

4.Meet-in-the-Middle

python

复制

下载

def meet_in_middle(n, target): half = n // 2 left_sums = {} # 枚举前半部分 for mask in range(1 << half): s = sum(nums[i] for i in range(half) if mask & (1 << i)) left_sums[s] = left_sums.get(s, 0) + 1 # 枚举后半部分 result = 0 for mask in range(1 << (n - half)): s = sum(nums[half + i] for i in range(n - half) if mask & (1 << i)) if target - s in left_sums: result += left_sums[target - s] return result

篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】

五、实战技巧总结

1.空间优化优先级

text

复制

下载

位运算压缩 → 滚动数组 → 按块处理 → 状态哈希

2.时间优化策略

预处理合法状态和转移
使用位运算加速状态检查
剪枝无效状态
使用对称性减少状态数

3.常见易错点

python

复制

下载

# 错误：忘记处理空集 subset = mask while True: # 这样会跳过空集 # ... if subset == 0: break subset = (subset - 1) & mask # 正确：显式处理空集 subset = mask while subset: # ... subset = (subset - 1) & mask # 处理空集 process(0)

六、复杂度分析

问题类型	状态数	常见复杂度	优化目标
普通状态压缩	O(2^n)	O(2^n * n)	减少n或优化转移
带约束压缩	O(有效状态)	O(状态数²)	预处理合法状态
多维压缩	O(2^(n*m))	指数级	Meet-in-Middle