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

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], capacity1): 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 * 22.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]*(capacity1) 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 位运算优化对于状态空间较小的问题如n20可用二进制位表示状态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 状态转移验证表构建二维表格验证转移逻辑物品\容量01234无物品00000物品A(3,4)00044物品B(2,3)00344物品C(1,1)013455.2 反向追踪解路径i, j n, capacity while i 0 and j 0: if dp[i][j] ! dp[i-1][j]: print(fSelect item {i}) j - w[i] i - 16. 复杂状态设计案例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 俄罗斯套娃信封先按宽度升序、高度降序排序再对高度序列求LISenvelopes.sort(keylambda 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(maxsizeNone) def dfs(i, j): if i n: return 0 if j -1: return float(-inf) res dfs(i1, j) if j nums[i]: res max(res, dfs(i1, j-nums[i]) values[i]) return res7.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, (costw, v, new_s))8. 动态规划优化策略8.1 四边形不等式优化对于形如dp[i][j] min(dp[i][k] dp[k1][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[i1] dp[q[0]] cost(q[0], i)9. 动态规划在工程中的应用9.1 文本对齐问题def justify(words, maxWidth): n len(words) dp [0]*(n1) for i in range(1,n1): dp[i] dp[i-1] (len(words[i-1]) (i1)) 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 ( *(gap1)).join(line[:extra1]) *gap ( *(gap1)).join(line[extra1:]) i 0 for j in range(1,n1): if dp[j] - dp[i] - (ji1) maxWidth: res.append(construct(i,j-1)) i j-1 res.append(construct(i,n)) return res9.2 资源分配问题def allocate(resources, projects): n len(projects) dp [[0]*(resources1) for _ in range(n1)] for i in range(1, n1): cost, profit projects[i-1] for j in range(resources1): 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_casedp[...][0] 和 dp[0][...] 的初始值转移方程找出状态间的递推关系注意考虑所有可能的转移路径处理特殊情况如越界、边界条件遍历顺序根据依赖关系确定自顶向下记忆化搜索自底向上迭代填表特殊顺序如斜向遍历、按特定拓扑序等结果提取从最终状态回溯或直接获取结果实战建议先写暴力递归再添加记忆化最后改写成迭代形式。对于复杂问题可以先用注释写出状态定义和转移方程伪代码再实现具体细节。