动态规划（Dynamic Programming）是解决复杂优化问题的核心技术，也是算法领域的明珠。本文将深入探讨Python实现动态规划的全方位技术，涵盖基础概念、经典问题、优化技巧和实际工程应用，带您掌握这一强大工具的精髓。

一、动态规划的本质：最优决策的艺术

动态规划不是简单的编程技巧，而是一种系统化的决策方法论。其核心思想是理查德·贝尔曼提出的"最优性原理"：一个多阶段决策过程的最优策略具有这样的性质，即无论初始状态和初始决策如何，其余决策必须构成最优策略。

动态规划三大特征：

1. 重叠子问题：问题可分解为重复计算的子问题

2. 最优子结构：问题最优解包含子问题最优解

3. 无后效性：当前决策不影响先前状态

# 斐波那契数列的递归与DP对比
def fib_recursive(n):if n <= 1: return nreturn fib_recursive(n-1) + fib_recursive(n-2)  # 指数级复杂度def fib_dp(n):if n == 0: return 0dp = [0] * (n+1)dp[1] = 1for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2]  # 线性复杂度return dp[n]# 测试：n=40
%timeit fib_recursive(40)  # 约10秒
%timeit fib_dp(40)        # 约0.5微秒

二、动态规划四步解题框架

步骤1：定义状态

• 明确dp数组含义

• 确定状态变量和维度

步骤2：建立状态转移方程

• 找到状态间递推关系

• 数学化表示最优子结构

步骤3：初始化边界条件

• 设置初始状态值

• 处理特殊情况

步骤4：确定计算顺序

• 自底向上或自顶向下

• 确保无后效性

def coin_change(coins, amount):"""零钱兑换问题：最少硬币数"""# 步骤1：定义状态 - dp[i]表示金额i的最小硬币数dp = [float('inf')] * (amount+1)# 步骤2：初始化边界 - 金额0需要0枚硬币dp[0] = 0# 步骤3：状态转移for coin in coins:for i in range(coin, amount+1):dp[i] = min(dp[i], dp[i-coin] + 1)# 步骤4：返回结果return dp[amount] if dp[amount] != float('inf') else -1# 测试
print(coin_change([1, 2, 5], 11))  # 输出：3 (5+5+1)

三、经典动态规划问题精解

3.1 背包问题：组合优化的基石

0-1背包问题：

def knapsack_01(weights, values, capacity):n = len(weights)# dp[i][w] 前i个物品放入容量w的最大价值dp = [[0]*(capacity+1) for _ in range(n+1)]for i in range(1, n+1):for w in range(1, capacity+1):if weights[i-1] <= w:dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])else:dp[i][w] = dp[i-1][w]return dp[n][capacity]# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity))  # 输出：10 (物品2+4)

完全背包问题：

def knapsack_unbounded(weights, values, capacity):dp = [0] * (capacity+1)for w in range(1, capacity+1):for i in range(len(weights)):if weights[i] <= w:dp[w] = max(dp[w], dp[w-weights[i]] + values[i])return dp[capacity]# 测试
print(knapsack_unbounded(weights, values, capacity))  # 输出：12 (物品1*4)

3.2 最长公共子序列（LCS）

def longest_common_subsequence(text1, text2):m, n = len(text1), len(text2)# dp[i][j] 表示text1[0:i]和text2[0:j]的LCS长度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] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])# 回溯构造LCSlcs = []i, j = m, nwhile i > 0 and j > 0:if text1[i-1] == text2[j-1]:lcs.append(text1[i-1])i -= 1j -= 1elif dp[i-1][j] > dp[i][j-1]:i -= 1else:j -= 1return dp[m][n], ''.join(reversed(lcs))# 测试
text1 = "abcde"
text2 = "ace"
length, seq = longest_common_subsequence(text1, text2)
print(f"长度: {length}, 序列: {seq}")  # 长度: 3, 序列: "ace"

3.3 最短编辑距离

def min_edit_distance(word1, word2):m, n = len(word1), len(word2)dp = [[0]*(n+1) for _ in range(m+1)]# 初始化边界for i in range(1, m+1):dp[i][0] = ifor j in range(1, n+1):dp[0][j] = j# 状态转移for i in range(1, m+1):for j in range(1, n+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i-1][j] + 1,    # 删除dp[i][j-1] + 1,    # 插入dp[i-1][j-1] + 1   # 替换)return dp[m][n]# 测试
print(min_edit_distance("horse", "ros"))  # 输出：3 (h->r, 删o, 删e)