动态规划详解：从入门到精通
一、什么是动态规划
动态规划（Dynamic Programming，简称DP）是一种将复杂问题分解为更小的子问题来求解的算法思想。它特别适用于具有重叠子问题和最优子结构性质的问题。
核心思想
分解问题：将原问题分解为若干个子问题
存储中间结果：避免重复计算子问题
构建最终解：从子问题的解构建原问题的解
二、动态规划的核心要素
- 最优子结构
一个问题的最优解包含其子问题的最优解。
示例：最短路径问题
如果从A到C的最短路径经过B，那么从A到B和从B到C的路径也分别是各自的最短路径。
- 重叠子问题
在递归求解过程中，相同的子问题会被多次计算。
示例：斐波那契数列
计算F(5)需要计算F(4)和F(3)
计算F(4)需要计算F(3)和F(2)
F(3)被重复计算
三、动态规划的两种实现方法
- 自顶向下（记忆化搜索，Memoization）
deffibonacci_memoization(n,memo=None):"""自顶向下：记忆化搜索"""ifmemoisNone:memo={}# 如果已经计算过，直接返回ifninmemo:returnmemo[n]# 基本情况ifn<=1:returnn# 递归计算并存储结果memo[n]=fibonacci_memoization(n-1,memo)+fibonacci_memoization(n-2,memo)returnmemo[n]# 测试print("斐波那契数列（记忆化搜索）:")foriinrange(10):print(f"F({i}) ={fibonacci_memoization(i)}")- 自底向上（制表法，Tabulation）
deffibonacci_tabulation(n):"""自底向上：制表法"""ifn<=1:returnn# 创建DP表dp=[0]*(n+1)dp[1]=1# 填充DP表foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]deffibonacci_optimized(n):"""空间优化的斐波那契"""ifn<=1:returnn prev2,prev1=0,1# F(0), F(1)foriinrange(2,n+1):current=prev1+prev2 prev2,prev1=prev1,currentreturnprev1# 测试print("\n斐波那契数列（制表法）:")foriinrange(10):print(f"F({i}) ={fibonacci_tabulation(i)}")四、经典动态规划问题
- 0-1背包问题
defknapsack_01(weights,values,capacity):""" 0-1背包问题 weights: 物品重量列表 values: 物品价值列表 capacity: 背包容量 """n=len(weights)# 创建DP表：dp[i][w]表示前i个物品在容量w下的最大价值dp=[[0]*(capacity+1)for_inrange(n+1)]# 填充DP表foriinrange(1,n+1):forwinrange(1,capacity+1):# 如果不选第i个物品dp[i][w]=dp[i-1][w]# 如果选第i个物品（前提是容量足够）ifweights[i-1]<=w:dp[i][w]=max(dp[i][w],dp[i-1][w-weights[i-1]]+values[i-1])# 回溯找出选择的物品selected_items=[]w=capacityforiinrange(n,0,-1):ifdp[i][w]!=dp[i-1][w]:selected_items.append(i-1)w-=weights[i-1]returndp[n][capacity],selected_items[::-1]# 测试weights=[2,3,4,5]values=[3,4,5,6]capacity=8max_value,items=knapsack_01(weights,values,capacity)print(f"\n0-1背包问题:")print(f"最大价值:{max_value}")print(f"选择的物品索引:{items}")- 最长公共子序列（LCS）
deflongest_common_subsequence(text1,text2):""" 最长公共子序列 返回LCS的长度和序列 """m,n=len(text1),len(text2)# dp[i][j]表示text1[0:i]和text2[0:j]的LCS长度dp=[[0]*(n+1)for_inrange(m+1)]# 填充DP表foriinrange(1,m+