动态规划 (Dynamic Programming) 算法概念-Python示例

Python 实例详解

1. 斐波那契数列

# 传统递归方法 - 效率低下 O(2^n)def fibonacci_recursive(n): if n <= 1: return n return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)# 动态规划方法 - 时间复杂度 O(n)，空间复杂度 O(n)def fibonacci_dp(n): if n <= 1: return n # 创建状态数组 dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 # 状态转移 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]# 空间优化版本 - 空间复杂度 O(1)def fibonacci_optimized(n): if n <= 1: return n prev2, prev1 = 0, 1 for i in range(2, n + 1): current = prev1 + prev2 prev2, prev1 = prev1, current return prev1

2. 硬币找零问题

# 找到组成金额所需的最少硬币数def coin_change(coins, amount): # dp[i] 表示组成金额 i 所需的最少硬币数 dp = [float(\'inf\')] * (amount + 1) dp[0] = 0 # 组成金额0需要0个硬币 # 对于每个金额 for i in range(1, amount + 1): # 尝试每种硬币 for coin in coins: if coin <= i: # 状态转移方程 dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float(\'inf\') else -1# 示例使用print(coin_change([1, 3, 4], 6)) # 输出: 2 (3+3)

3. 编辑距离问题

# 计算两个字符串之间的最小编辑距离def min_distance(word1, word2): m, n = len(word1), len(word2) # dp[i][j] 表示 word1[0...i-1] 转换为 word2[0...j-1] 的最小操作数 dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界条件 for i in range(m + 1): dp[i][0] = i for j in range(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]

4. 最长递增子序列

# 找到数组中最长递增子序列的长度def length_of_lis(nums): if not nums: return 0 # dp[i] 表示以 nums[i] 结尾的最长递增子序列长度 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)# 优化版本 - 使用二分查找 O(n log n)def length_of_lis_optimized(nums): import bisect tails = [] for num in nums: # 二分查找插入位置 pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) else: tails[pos] = num return len(tails)

5. 背包问题

# 0-1背包问题：在限定重量下获取最大价值def knapsack(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(capacity + 1): # 不选择第i个物品 dp[i][w] = dp[i - 1][w] # 如果能选择第i个物品，比较选择和不选择的价值 if w >= weights[i - 1]: dp[i][w] = max(  dp[i][w],  dp[i - 1][w - weights[i - 1]] + values[i - 1] ) return dp[n][capacity]# 空间优化版本def knapsack_optimized(weights, values, capacity): n = len(weights) # 只需要一维数组，从后往前更新避免重复使用 dp = [0] * (capacity + 1) for i in range(n): for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[capacity]

6. 最大子数组和

# 求连续子数组的最大和def max_subarray(nums): if not nums: return 0 # dp[i] 表示以第i个元素结尾的最大子数组和 dp = [0] * len(nums) dp[0] = nums[0] max_sum = dp[0] # 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i]) for i in range(1, len(nums)): dp[i] = max(nums[i], dp[i - 1] + nums[i]) max_sum = max(max_sum, dp[i]) return max_sum# 空间优化版本def max_subarray_optimized(nums): if not nums: return 0 max_sum = nums[0] current_sum = nums[0] for i in range(1, len(nums)): current_sum = max(nums[i], current_sum + nums[i]) max_sum = max(max_sum, current_sum) return max_sum

实际应用场景

1. 计算机科学领域

• 算法优化：在递归算法中避免重复计算
• 字符串处理：文本编辑器的差异比较、拼写检查
• 图形处理：图像压缩、模式识别
• 编译器设计：语法分析、代码优化

2. 业务应用

• 资源分配：项目管理中的任务调度
• 金融领域：投资组合优化、风险评估
• 电商推荐：个性化推荐系统
• 物流运输：路径规划、库存管理

3. 生物信息学

• DNA序列比对：基因序列相似性分析
• 蛋白质结构预测：生物分子结构分析

4. 游戏开发

• AI决策：游戏中的路径寻找
• 关卡设计：难度平衡计算

5. 网络通信

• 路由算法：网络数据包的最优路径选择
• 数据压缩：文件压缩算法优化

动态规划解题模板

def dynamic_programming_solution(problem): # 1. 定义状态 # dp[i] 或 dp[i][j] 表示什么含义 # 2. 初始化边界条件 # dp[0] = ..., dp[1] = ... # 3. 状态转移方程 # for i in range(...): # dp[i] = some_function(dp[i-1], dp[i-2], ...) # 4. 返回结果 # return dp[n] 或其他形式