用二进制压缩状态空间——指数级问题的多项式解法
当DP状态包含"哪些元素已被选/访问"时，用二进制位表示选择状态，将2^n个状态压缩为整数，这就是状态压缩DP（bitmask DP）。它让指数级的状态空间变得可处理。
def bitmask_dp(n):
full_mask = (1 << n) - 1 # 全部选中的状态
dp = [初始值] * (1 << n) # dp[mask] = 状态mask下的最优解
for mask in range(1 << n):
for i in range(n):
if mask & (1 << i): # 第i位已选
prev = mask ^ (1 << i) # 去掉第i位的前驱
dp[mask] = optimize(dp[mask], dp[prev] + cost[i])
return dp[full_mask]| 特征 | 是否适合状态压缩 |
|---|---|
| n <= 20 | 2^20 = 100万，可接受 |
| n <= 25 | 2^25 = 3200万，需要优化 |
| n > 25 | 状态空间太大，不适合 |
| 状态是选/不选的集合 | 天然适合bitmask |
| 需要枚举子集 | bitmask子集枚举很高效 |
给定无向图，返回能访问所有节点的最短路径长度。
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
if n == 1:
return 0
target = (1 << n) - 1
visited = set()
queue = deque()
for i in range(n):
queue.append((i, 1 << i, 0))
visited.add((i, 1 << i))
while queue:
node, mask, dist = queue.popleft()
for neighbor in graph[node]:
new_mask = mask | (1 << neighbor)
if new_mask == target:
return dist + 1
if (neighbor, new_mask) not in visited:
visited.add((neighbor, new_mask))
queue.append((neighbor, new_mask, dist + 1))
return 0时间: O(n * 2^n) 空间: O(n * 2^n)
给定座位矩阵，学生不能看到左边、右边、左前、右前方的答案，求最多能坐多少学生。
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
m, n = len(seats), len(seats[0])
valid_rows = []
for row in seats:
mask = 0
for j in range(n):
if row[j] == '.':
mask |= (1 << j)
valid_rows.append(mask)
dp = [{} for _ in range(m)]
for mask in range(1 << n):
if (mask & valid_rows[0]) != mask: continue
if mask & (mask >> 1): continue
dp[0][mask] = bin(mask).count('1')
for i in range(1, m):
for mask in range(1 << n):
if (mask & valid_rows[i]) != mask: continue
if mask & (mask >> 1): continue
cnt = bin(mask).count('1')
for prev_mask in dp[i-1]:
if (mask & (prev_mask >> 1)) or (mask & (prev_mask << 1)):
continue
dp[i][mask] = max(dp[i].get(mask, 0), dp[i-1][prev_mask] + cnt)
return max(dp[m-1].values()) if dp[m-1] else 0时间: O(m * 2^n * 2^n) 空间: O(m * 2^n)
两个玩家轮流从1到maxChoosableInteger中选一个数（不可重复选），先使累计和>=desiredTotal的玩家获胜。
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal:
return False
if desiredTotal <= 0:
return True
memo = {}
def dfs(remaining, used):
if remaining <= 0:
return False
if used in memo:
return memo[used]
for i in range(1, maxChoosableInteger + 1):
bit = 1 << (i - 1)
if used & bit: continue
if not dfs(remaining - i, used | bit):
memo[used] = True
return True
memo[used] = False
return False
return dfs(desiredTotal, 0)时间: O(n * 2^n) 空间: O(2^n)
在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：
# 通用解题模板
class Solution:
def solve(self, input_data):
# 1. 边界检查
if not input_data:
return default_value
# 2. 初始化
result = initial_value
state = initial_state
# 3. 主循环
for item in input_data:
state = transition(state, item)
result = max/min/update(result, state)
# 4. 返回结果
return result每道经典题目都有丰富的变体。掌握核心模板后，灵活应对变体才是面试的真正挑战。以下列举本课相关的高频变体和扩展思路。
# 面试沟通模板
# 1. 先说思路（1-2分钟）
"这道题我想到两种解法，先说更直观的一种..."
# 2. 分析复杂度（30秒）
"时间复杂度O(n^2)，空间可以优化到O(n)"
# 3. 边写边说
"这里我定义dp[i]表示...，转移方程是..."
# 4. 主动验证
"我用示例走一遍：dp[0]=..., dp[1]=..."
# 5. 讨论优化
"空间还可以进一步优化，因为dp[i]只依赖..."| 检查项 | 常见错误 |
|---|---|
| 初始条件 | dp[0]是否正确？空输入是否处理？ |
| 遍历范围 | 循环从0还是1开始？是否越界？ |
| 状态转移 | 依赖的状态是否已计算？ |
| 返回值 | 是dp[n]还是max(dp)？ |
| 边界情况 | 单元素、全相同、空数组 |