动态规划核心思想与工程实践详解-平芜编程栈

1. 动态规划核心思想回顾

动态规划（Dynamic Programming）作为算法设计中的重要方法论，其本质是通过将复杂问题分解为相互重叠的子问题，并存储子问题的解以避免重复计算。在part09这个阶段，我们需要深入理解三个关键特征：

最优子结构：问题的最优解包含其子问题的最优解
重叠子问题：不同的问题求解路径会重复遇到相同的子问题
状态转移方程：明确如何从较小问题的解推导出较大问题的解

关键认知：动态规划不是简单的"空间换时间"，而是通过系统化的状态定义和转移，将指数级复杂度降为多项式级别

2. 经典问题深度剖析

2.1 背包问题的变种实战

0-1背包的标准转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

但在实际工程中会遇到多种变体：

完全背包（物品无限取用）：

for i in range(n): for j in range(w[i], capacity+1): dp[j] = max(dp[j], dp[j - w[i]] + v[i])

多重背包（物品有限个）：

while k <= s[i]: for j in range(capacity, k*w[i]-1, -1): dp[j] = max(dp[j], dp[j - k*w[i]] + k*v[i]) s[i] -= k k *= 2

2.2 股票买卖问题状态机解法

这类问题通常需要定义多个状态：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) # 空仓状态 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) # 持仓状态

对于含冷却期的情况，需要增加状态维度：

dp[i][0] = max(dp[i-1][0], dp[i-1][2]) # 休息后空仓 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) # 买入 dp[i][2] = dp[i-1][1] + prices[i] # 卖出

3. 状态压缩进阶技巧

3.1 滚动数组优化

当状态转移只依赖前一轮结果时，可将二维数组压缩为一维：

dp = [0]*(capacity+1) for i in range(n): for j in range(capacity, w[i]-1, -1): # 必须逆序 dp[j] = max(dp[j], dp[j-w[i]] + v[i])

3.2 位运算优化

对于状态空间较小的问题（如n<=20），可用二进制位表示状态：

mask = 1 << n dp = [float('inf')] * mask dp[0] = 0 for state in range(mask): if dp[state] == float('inf'): continue for i in range(n): if not (state & (1 << i)): new_state = state | (1 << i) dp[new_state] = min(dp[new_state], dp[state] + cost[i])

4. 树形动态规划实战

4.1 二叉树抢劫问题

定义两个状态：

dp[0][u]：不抢u节点时的最大收益
dp[1][u]：抢劫u节点时的最大收益

def dfs(u): if not u: return (0, 0) left = dfs(u.left) right = dfs(u.right) rob = u.val + left[0] + right[0] not_rob = max(left) + max(right) return (not_rob, rob)

4.2 公司派对问题

每个员工有快乐值，直属上下级不能同时参加：

def dfs(u): attend = happy[u] not_attend = 0 for v in subordinates[u]: a, na = dfs(v) attend += na not_attend += max(a, na) return (attend, not_attend)

5. 动态规划调试方法论

5.1 状态转移验证表

构建二维表格验证转移逻辑：

物品\容量	1	2	3	4
无物品	0	0	0	0
物品A(3,4)	0	0	4	4
物品B(2,3)	0	3	4	4
物品C(1,1)	1	3	4	5

5.2 反向追踪解路径

i, j = n, capacity while i > 0 and j > 0: if dp[i][j] != dp[i-1][j]: print(f"Select item {i}") j -= w[i] i -= 1

6. 复杂状态设计案例

6.1 正则表达式匹配

dp[i][j] 表示s前i个与p前j个是否匹配 if p[j-1] == '*': dp[i][j] = dp[i][j-2] or (match(s[i-1],p[j-2]) and dp[i-1][j]) else: dp[i][j] = match(s[i-1],p[j-1]) and dp[i-1][j-1]

6.2 俄罗斯套娃信封

先按宽度升序、高度降序排序，再对高度序列求LIS：

envelopes.sort(key=lambda x: (x[0], -x[1])) tails = [] for w, h in envelopes: idx = bisect.bisect_left(tails, h) if idx == len(tails): tails.append(h) else: tails[idx] = h return len(tails)

7. 动态规划与其他算法的结合

7.1 记忆化搜索实现

from functools import lru_cache @lru_cache(maxsize=None) def dfs(i, j): if i == n: return 0 if j == -1: return float('-inf') res = dfs(i+1, j) if j >= nums[i]: res = max(res, dfs(i+1, j-nums[i]) + values[i]) return res

7.2 与Dijkstra算法的结合

处理带状态的最短路径问题：

heap = [(0, start, state)] dist = defaultdict(lambda: float('inf')) while heap: cost, u, s = heapq.heappop(heap) if u == target and check_state(s): return cost for v, w in graph[u]: new_s = transition(s, v) if cost + w < dist[(v, new_s)]: dist[(v, new_s)] = cost + w heapq.heappush(heap, (cost+w, v, new_s))

8. 动态规划优化策略

8.1 四边形不等式优化

对于形如：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i,j))

当cost函数满足四边形不等式时，可将O(n^3)优化为O(n^2)

8.2 单调队列优化

处理滑动窗口最值问题：

q = deque() for i in range(n): while q and dp[q[-1]] >= dp[i]: q.pop() q.append(i) while q[0] <= i - k: q.popleft() dp[i+1] = dp[q[0]] + cost(q[0], i)

9. 动态规划在工程中的应用

9.1 文本对齐问题

def justify(words, maxWidth): n = len(words) dp = [0]*(n+1) for i in range(1,n+1): dp[i] = dp[i-1] + (len(words[i-1]) + (i>1)) res = [] def construct(i,j): line = words[i:j] if len(line) == 1 or j == n: return ' '.join(line).ljust(maxWidth) spaces = maxWidth - sum(len(w) for w in line) gap, extra = divmod(spaces, len(line)-1) return (' '*(gap+1)).join(line[:extra+1]) + ' '*gap + (' '*(gap+1)).join(line[extra+1:]) i = 0 for j in range(1,n+1): if dp[j] - dp[i] - (j>i+1) > maxWidth: res.append(construct(i,j-1)) i = j-1 res.append(construct(i,n)) return res

9.2 资源分配问题

def allocate(resources, projects): n = len(projects) dp = [[0]*(resources+1) for _ in range(n+1)] for i in range(1, n+1): cost, profit = projects[i-1] for j in range(resources+1): if j < cost: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost] + profit) # 回溯找出选择的项目 res = [] j = resources for i in range(n, 0, -1): if dp[i][j] != dp[i-1][j]: res.append(i-1) j -= projects[i-1][0] return dp[n][resources], res[::-1]

10. 动态规划解题框架总结

状态定义：明确dp数组的含义，通常为：
- 一维：dp[i]表示前i个元素的状态
- 二维：dp[i][j]表示涉及两个维度的状态
初始化：设置边界条件，如：
- dp[0] = base_case
- dp[...][0] 和 dp[0][...] 的初始值
转移方程：找出状态间的递推关系，注意：
- 考虑所有可能的转移路径
- 处理特殊情况（如越界、边界条件）
遍历顺序：根据依赖关系确定：
- 自顶向下：记忆化搜索
- 自底向上：迭代填表
- 特殊顺序：如斜向遍历、按特定拓扑序等
结果提取：从最终状态回溯或直接获取结果

实战建议：先写暴力递归，再添加记忆化，最后改写成迭代形式。对于复杂问题，可以先用注释写出状态定义和转移方程伪代码，再实现具体细节。

动态规划核心思想与工程实践详解