一、状态压缩：把复杂状态装进小口袋
动态规划最让人头疼的就是状态爆炸问题。比如棋盘类问题，用传统方法表示每个格子的状态会导致内存爆炸。这时候就需要状态压缩——用二进制数表示状态，像把一整个棋盘塞进牛仔裤口袋。
举个例子，经典的「旅行商问题」中，我们需要记录哪些城市已经访问过。假设有5个城市：
# 技术栈：Python
# 用二进制位表示访问状态，1表示已访问
visited = 0b00000 # 初始状态
visited |= 0b00001 # 访问第1个城市（二进制从右往左数）
visited |= 0b00100 # 再访问第3个城市
print(bin(visited)) # 输出0b00101
实战案例：LeetCode 464「我能赢吗」问题。我们需要记录哪些数字已被选用：
# 技术栈：Python
def canIWin(maxNum, target):
memo = {}
def dfs(used, remaining):
if remaining <= 0: return False
if used in memo: return memo[used]
for i in range(1, maxNum+1):
if not (used & (1 << i)): # 检查数字i是否可用
if not dfs(used | (1 << i), remaining - i): # 对手不能赢
memo[used] = True
return True
memo[used] = False
return False
return dfs(0, target)
注意事项：
- 状态值范围不能太大（通常≤20位）
- 位运算优先级容易出错，建议多用括号
- 结合记忆化存储提升效率
二、区间DP：像剥洋葱一样拆解问题
当问题可以分解为连续子序列时，区间DP就是你的瑞士军刀。它的核心思想是：先解决小区间问题，再合并成大区间解。
典型场景包括：
- 字符串回文处理
- 矩阵链乘法
- 石子合并游戏
来看个石子合并的例子：
# 技术栈：Python
def stoneGame(piles):
n = len(piles)
dp = [[0]*n for _ in range(n)]
prefix = [0]*(n+1)
# 计算前缀和
for i in range(n):
prefix[i+1] = prefix[i] + piles[i]
# 区间长度从2开始
for l in range(2, n+1): # 区间长度
for i in range(n-l+1): # 区间起点
j = i + l - 1 # 区间终点
dp[i][j] = float('inf')
# 枚举分割点
for k in range(i, j):
cost = prefix[j+1] - prefix[i]
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)
return dp[0][n-1]
关键技巧：
- 先枚举区间长度，再枚举起点
- 使用前缀和快速计算区间和
- 注意边界条件（如l=1时的情况）
三、树形DP：在枝丫间穿梭的思维
处理树结构时，常规DP方法会失效，因为树具有递归特性。这时候需要采用后序遍历（先处理子树，再处理根节点）的策略。
举个经典问题：二叉树中的最大路径和
# 技术栈：Python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxPathSum(root):
res = -float('inf')
def dfs(node):
nonlocal res
if not node: return 0
# 递归处理左右子树
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
# 更新全局最大值
res = max(res, left + right + node.val)
# 返回当前子树能提供的最大值
return max(left, right) + node.val
dfs(root)
return res
常见陷阱：
- 忘记处理空子树
- 没有正确传递子树信息
- 混淆节点值与路径和的概念
四、综合实战：三种DP的混合应用
真实场景中往往需要组合使用这些技术。比如下面这个「监控二叉树」问题，就需要状态压缩+树形DP：
# 技术栈：Python
def minCameraCover(root):
# 定义三种状态：
# 0: 未被监控
# 1: 被监控但无摄像头
# 2: 有摄像头
res = 0
def dfs(node):
nonlocal res
if not node: return 1
left = dfs(node.left)
right = dfs(node.right)
# 如果任一子节点未被监控
if left == 0 or right == 0:
res += 1
return 2
# 如果任一子节点有摄像头
if left == 2 or right == 2:
return 1
# 否则当前节点未被监控
return 0
if dfs(root) == 0:
res += 1
return res
应用场景对比： | DP类型 | 适用场景 | 时间复杂度 | 空间复杂度 | |-------------|-------------------------|---------------|---------------| | 状态压缩 | 小规模离散状态 | O(n*2^n) | O(2^n) | | 区间DP | 线性序列问题 | O(n^3) | O(n^2) | | 树形DP | 树/图结构问题 | O(n) | O(h) |
技术优缺点：
- 状态压缩：节省空间但可读性差
- 区间DP：思路直观但代码量大
- 树形DP：递归思维要求高但代码简洁
终极建议：
- 先画状态转移图再写代码
- 从小规模测试案例开始验证
- 合理使用记忆化存储避免重复计算
- 注意Python的递归深度限制（可改用栈实现）
评论