动态规划：从递归到最优决策的算法艺术
动态规划Dynamic Programming简称 DP并非某种具体的算法而是一种将复杂问题分解为简单子问题、并通过存储子问题的解来避免重复计算的算法设计思想。其核心哲学在于用空间换时间解决那些具有最优子结构和重叠子问题特性的难题。不同于贪心算法的局部最优选择动态规划通过穷举所有可能的决策路径确保找到全局最优解。要理解动态规划不妨从最朴素的递归说起。以经典的斐波那契数列为例其数学定义为F(n)F(n−1)F(n−2)F(n) F(n-1) F(n-2)F(n)F(n−1)F(n−2)其中F(0)0,F(1)1F(0)0, F(1)1F(0)0,F(1)1。若直接翻译为递归代码我们会发现计算过程产生了指数级的冗余运算。例如在计算F(5)F(5)F(5)时F(3)F(3)F(3)被重复计算了多次。这种重叠子问题现象导致了巨大的性能浪费。动态规划介入的方式便是引入一个数组dpdpdp来存储已计算的结果这被称为“记忆化搜索”。在正式的文章中我们通常使用“自底向上”的迭代方式来构建 DP。对于斐波那契数列我们定义状态dp[i]dp[i]dp[i]表示第iii个数字的值。状态转移方程为dp[i]dp[i−1]dp[i−2] dp[i] dp[i-1] dp[i-2]dp[i]dp[i−1]dp[i−2]通过初始化dp[0]dp[0]dp[0]和dp[1]dp[1]dp[1]我们可以线性地推导出后续结果。以下是标准的动态规划实现deffibonacci(n:int)-int:ifn1:returnn# 定义 dp 数组dp[0]*(n1)# 初始化边界条件dp[0],dp[1]0,1# 状态转移foriinrange(2,n1):dp[i]dp[i-1]dp[i-2]returndp[n]此代码的时间复杂度为O(n)O(n)O(n)空间复杂度为O(n)O(n)O(n)。进一步观察可以发现dp[i]dp[i]dp[i]仅依赖于前两个状态因此我们可以将空间压缩至O(1)O(1)O(1)deffibonacci_optimized(n:int)-int:ifn1:returnn prev,curr0,1for_inrange(2,n1):prev,currcurr,prevcurrreturncurr动态规划的难点在于状态定义与转移方程的设计。以0-1 背包问题为例这是动态规划中的里程碑式问题。问题描述如下给定nnn个物品每个物品重量为wiw_iwi价值为viv_ivi以及一个容量为WWW的背包。求在不超过容量限制的前提下背包能装下的物品最大总价值。我们定义二维状态dp[i][j]dp[i][j]dp[i][j]表示前iii个物品放入容量为jjj的背包中所能获得的最大价值。对于每个物品我们有两种选择放或不放。如果不放则dp[i][j]dp[i−1][j]dp[i][j] dp[i-1][j]dp[i][j]dp[i−1][j]如果放前提是j≥wij \ge w_ij≥wi则dp[i][j]dp[i−1][j−wi]vidp[i][j] dp[i-1][j-w_i] v_idp[i][j]dp[i−1][j−wi]vi。综合二者状态转移方程为dp[i][j]max(dp[i−1][j],dp[i−1][j−wi]vi) dp[i][j] \max(dp[i-1][j], dp[i-1][j-w_i] v_i)dp[i][j]max(dp[i−1][j],dp[i−1][j−wi]vi)完整的代码如下defknapsack_01(W,weights,values):nlen(weights)# dp[i][j] 表示前 i 个物品容量为 j 的最大价值dp[[0]*(W1)for_inrange(n1)]foriinrange(1,n1):forjinrange(W1):# 不拿第 i 个物品dp[i][j]dp[i-1][j]# 尝试拿第 i 个物品ifjweights[i-1]:dp[i][j]max(dp[i][j],dp[i-1][j-weights[i-1]]values[i-1])returndp[n][W]同样该问题也可以进行空间优化。由于dp[i]dp[i]dp[i]只依赖于dp[i−1]dp[i-1]dp[i−1]我们可以使用一维数组并从后往前遍历容量jjj以避免数据覆盖。除了背包问题动态规划还广泛应用于字符串处理如最长公共子序列LCS、区间决策如石子合并以及树形结构树形 DP。掌握动态规划的关键在于“勤画表”通过在草稿纸上模拟dpdpdp数组的填充过程往往能直观地发现状态之间的联系。总而言之动态规划不是一蹴而就的技巧而是对问题本质的深度剖析。它要求我们明确“什么是状态”以及“状态如何流转”。当你面对一个问题时若能将其抽象为一个多阶段的决策过程并证明其满足无后效性那么动态规划很可能就是你手中的利刃。