Python 实现动态规划：3 步法解决多阶段决策问题（附最短路径代码）

Python 实现动态规划3 步法解决多阶段决策问题附最短路径代码动态规划Dynamic ProgrammingDP是解决复杂决策问题的利器尤其在处理具有重叠子问题和最优子结构特性的场景时表现突出。本文将带你从零开始用 Python 实现动态规划的经典三步法并通过最短路径问题展示完整代码实现。1. 动态规划核心思想动态规划的本质是将复杂问题分解为相互关联的子问题通过存储子问题的解避免重复计算。其核心在于以下两个特性最优子结构问题的最优解包含子问题的最优解重叠子问题不同决策路径会重复访问相同的子问题以多阶段图的最短路径为例从起点到终点的最优路径必然包含中间节点的最优路径。这就是典型的动态规划适用场景。2. 动态规划三步法框架2.1 定义状态状态是描述问题某个阶段情况的变量。对于最短路径问题我们定义# dp[i] 表示从节点i到终点的最短距离 dp [float(inf)] * num_nodes2.2 建立递推关系递推公式连接了不同状态之间的关系。对于最短路径dp[i] min(dp[i], weight[i][j] dp[j]) # 对所有相邻节点j2.3 确定边界条件边界条件给出了最简子问题的解dp[target] 0 # 终点到自身的距离为03. 多阶段图最短路径实现下面是一个完整的多阶段图最短路径Python实现def shortest_path(graph, stages, source, target): 多阶段图最短路径动态规划解法 :param graph: 邻接表表示的图 {node: {neighbor: weight}} :param stages: 每个节点所属的阶段 [stage0_nodes, stage1_nodes,...] :param source: 起点 :param target: 终点 :return: (最短距离, 路径) # 初始化 dp {node: float(inf) for node in graph} dp[target] 0 path {node: [] for node in graph} # 按阶段逆序计算 for stage in reversed(stages[:-1]): # 跳过最后阶段终点 for node in stage: # 遍历所有邻接节点 for neighbor, weight in graph[node].items(): if dp[node] weight dp[neighbor]: dp[node] weight dp[neighbor] path[node] [node] path[neighbor] return dp[source], path[source]使用示例# 定义多阶段图 graph { A: {B1: 5, B2: 3}, B1: {C1: 1, C2: 3, C3: 6}, B2: {C1: 8, C2: 4, C3: 2}, C1: {D1: 6, D2: 2}, C2: {D1: 3, D2: 5}, C3: {D1: 4, D2: 5}, D1: {E: 3}, D2: {E: 2}, E: {} } # 定义阶段划分 stages [ [A], # 阶段0 [B1, B2], # 阶段1 [C1, C2, C3], # 阶段2 [D1, D2], # 阶段3 [E] # 阶段4 ] distance, path shortest_path(graph, stages, A, E) print(f最短距离: {distance}) print(f最优路径: { - .join(path)})输出结果最短距离: 8 最优路径: A - B2 - C3 - D2 - E4. 动态规划优化技巧4.1 空间优化当状态转移只依赖有限的前驱状态时可以压缩DP表# 斐波那契数列的空间优化示例 def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b4.2 记忆化搜索递归实现配合缓存可以更直观from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n-1) fib(n-2)4.3 常见问题模式问题类型状态定义典型例题序列问题dp[i]表示前i个元素解最长递增子序列背包问题dp[i][w]表示前i物品w容量解0-1背包问题区间问题dp[i][j]表示区间i-j解矩阵链乘法状态机问题dp[i][s]表示第i步状态s解股票买卖问题5. 动态规划调试技巧打印DP表可视化中间结果for k, v in dp.items(): print(f{k}: {v})边界测试检查最小规模输入逐步验证手动计算前几步与程序输出对比可视化决策图用Graphviz等工具绘制状态转移提示在复杂问题中先用小规模数据验证递推公式的正确性再扩展到完整问题。动态规划的魅力在于它能将看似复杂的问题分解为可管理的子问题。通过定义清晰的状态和递推关系配合适当的边界条件许多困难问题都能找到高效的解决方案。