企业官网建设流程全解析

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

动态规划（Dynamic Programming，DP）是解决复杂决策问题的利器，尤其在处理具有重叠子问题和最优子结构特性的场景时表现突出。本文将带你从零开始，用 Python 实现动态规划的经典三步法，并通过最短路径问题展示完整代码实现。

1. 动态规划核心思想

动态规划的本质是将复杂问题分解为相互关联的子问题，通过存储子问题的解避免重复计算。其核心在于以下两个特性：

• 最优子结构：问题的最优解包含子问题的最优解
• 重叠子问题：不同决策路径会重复访问相同的子问题

以多阶段图的最短路径为例，从起点到终点的最优路径必然包含中间节点的最优路径。这就是典型的动态规划适用场景。

2. 动态规划三步法框架

2.1 定义状态

状态是描述问题某个阶段情况的变量。对于最短路径问题，我们定义：

# dp[i] 表示从节点i到终点的最短距离 dp = [float('inf')] * num_nodes

2.2 建立递推关系

递推公式连接了不同状态之间的关系。对于最短路径：

dp[i] = min(dp[i], weight[i][j] + dp[j]) # 对所有相邻节点j

2.3 确定边界条件

边界条件给出了最简子问题的解：

dp[target] = 0 # 终点到自身的距离为0

3. 多阶段图最短路径实现

下面是一个完整的多阶段图最短路径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 -> E

4. 动态规划优化技巧

4.1 空间优化

当状态转移只依赖有限的前驱状态时，可以压缩DP表：

# 斐波那契数列的空间优化示例 def fib(n): if n < 2: return n a, b = 0, 1 for _ in range(2, n+1): a, b = b, a + b return b

4.2 记忆化搜索

递归实现配合缓存可以更直观：

from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n < 2: return n return fib(n-1) + fib(n-2)

4.3 常见问题模式

5. 动态规划调试技巧

1. 打印DP表：可视化中间结果

   for k, v in dp.items(): print(f"{k}: {v}")

2. 边界测试：检查最小规模输入

3. 逐步验证：手动计算前几步与程序输出对比

4. 可视化决策图：用Graphviz等工具绘制状态转移

提示：在复杂问题中，先用小规模数据验证递推公式的正确性，再扩展到完整问题。

动态规划的魅力在于它能将看似复杂的问题分解为可管理的子问题。通过定义清晰的状态和递推关系，配合适当的边界条件，许多困难问题都能找到高效的解决方案。