动态规划五大经典问题实战解析：从理论到Python实现

动态规划（Dynamic Programming）作为算法设计中的核心思想，在解决优化问题时展现出强大的威力。本文将深入探讨五大经典动态规划问题，通过清晰的Python代码实现，帮助读者掌握这一重要算法范式。

1. 动态规划基础与核心思想

动态规划是一种分阶段解决问题的数学方法，由美国数学家理查德·贝尔曼在20世纪50年代提出。其核心在于将复杂问题分解为相互关联的子问题，通过保存子问题的解避免重复计算，显著提高算法效率。

动态规划三大特征：

• 最优子结构：问题的最优解包含子问题的最优解
• 重叠子问题：不同决策序列会重复访问相同的子问题
• 无后效性：未来决策只与当前状态有关，与过去决策无关

# 动态规划基本框架示例 def dp_template(): # 1. 定义状态 dp = [0] * n # 2. 初始化基础情况 dp[0] = base_case # 3. 状态转移 for i in range(1, n): dp[i] = transition(dp[i-1], ...) return dp[-1]

2. 最短路径问题

最短路径问题是动态规划的经典应用场景，Dijkstra算法和Floyd算法都是基于动态规划思想发展而来。

问题描述：给定带权有向图，求从起点到终点的最短路径。

状态转移方程：

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

def floyd(graph): n = len(graph) dist = [[float('inf')]*n for _ in range(n)] # 初始化 for i in range(n): for j in range(n): if i == j: dist[i][j] = 0 elif graph[i][j] != 0: dist[i][j] = graph[i][j] # 动态规划求解 for k in range(n): for i in range(n): for j in range(n): dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]) return dist

提示：Floyd算法时间复杂度为O(n³)，适合解决全源最短路径问题

3. 背包问题

背包问题展现了动态规划在资源分配中的强大能力，分为0-1背包和完全背包两种基本形式。

0-1背包状态转移方程：

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

def knapsack_01(weights, values, capacity): n = len(weights) dp = [[0]*(capacity+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, capacity+1): if weights[i-1] <= j: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]) else: dp[i][j] = dp[i-1][j] return dp[n][capacity] # 空间优化版本 def knapsack_01_optimized(weights, values, capacity): dp = [0]*(capacity+1) for i in range(len(weights)): for j in range(capacity, weights[i]-1, -1): dp[j] = max(dp[j], dp[j-weights[i]] + values[i]) return dp[capacity]

4. 最长公共子序列(LCS)

LCS问题展示了动态规划在序列比对中的应用，是生物信息学和文本处理的基础算法。

状态转移方程：

if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def longest_common_subsequence(text1, text2): m, n = len(text1), len(text2) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n]

5. 矩阵链乘法

矩阵链乘法问题展示了动态规划在优化计算顺序方面的应用，能显著减少矩阵相乘的计算量。

状态转移方程：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])

def matrix_chain_order(p): n = len(p) - 1 dp = [[0]*n for _ in range(n)] 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 = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1] if cost < dp[i][j]: dp[i][j] = cost return dp[0][n-1]

6. 资源分配问题

资源分配问题是动态规划在管理运筹学中的典型应用，用于优化有限资源的分配策略。

状态转移方程：

dp[i][j] = max(dp[i-1][k] + f(i, j-k)) for 0 ≤ k ≤ j

def resource_allocation(resources, projects, profit_func): dp = [[0]*(resources+1) for _ in range(projects+1)] for i in range(1, projects+1): for j in range(resources+1): max_val = 0 for k in range(j+1): current = dp[i-1][j-k] + profit_func(i, k) if current > max_val: max_val = current dp[i][j] = max_val return dp[projects][resources]

动态规划问题特征对比表：

7. 动态规划优化技巧

在实际应用中，我们常常需要对基本动态规划算法进行优化：

空间优化：很多情况下可以只保留必要状态，将空间复杂度从O(n²)降到O(n)

# 斐波那契数列的空间优化 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

记忆化搜索：采用递归+缓存的方式实现动态规划

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

状态压缩：使用位运算等技巧压缩状态表示

def tsp(graph): n = len(graph) dp = [[float('inf')]*n for _ in range(1<<n)] dp[1][0] = 0 for mask in range(1<<n): for u in range(n): if not (mask & (1<<u)): continue for v in range(n): if mask & (1<<v): continue new_mask = mask | (1<<v) dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + graph[u][v]) return min(dp[(1<<n)-1][u] + graph[u][0] for u in range(n))

掌握动态规划需要大量练习，从理解问题本质开始，逐步构建状态定义和转移方程。建议从简单问题入手，如爬楼梯、硬币兑换等，再逐步挑战更复杂的问题。