动态规划核心实现：备忘录法与自底向上法详解与实战

1. 项目概述从“暴力”到“优雅”的必经之路如果你刷过算法题或者在工作中处理过复杂的优化问题那么“动态规划”这四个字对你来说一定不陌生甚至可能带着一丝又爱又恨的情绪。爱的是它确实能解决那些看似无从下手的复杂问题恨的是状态转移方程想不明白代码写出来又慢又吃内存。今天我们不聊那些高深莫测的理论证明就聚焦在两个最核心、最实用的实现技巧上备忘录法和自底向上法。你可以把它们看作是解决动态规划问题的两把“瑞士军刀”一把从上往下“探索式”解决问题另一把从下往上“建设式”铺平道路。简单来说动态规划的核心思想是“记住已经解决过的子问题答案避免重复计算”。但怎么“记住”从哪里开始“记”这就是备忘录法和自底向上法的分野。前者我们称之为记忆化搜索它保留了递归的直观思维但用一张“备忘录”表格剪掉了重复的递归分支后者我们称之为经典的DP表格法它彻底抛弃递归从最小的子问题开始一步步迭代填满整个表格最终得到答案。理解这两者的区别、各自的适用场景以及内在的优化技巧是你能把动态规划从“看懂答案”提升到“随手写出高效解”的关键一步。无论你是正在备战面试的求职者还是需要优化业务逻辑的工程师掌握这两招都能让你在面对“最长上升子序列”、“01背包”这类经典问题时思路更清晰代码更稳健。2. 核心思路拆解两种哲学一种目标动态规划不是一种具体的算法而是一种方法论。它的目标始终如一通过最优子结构和重叠子问题避免重复计算提升效率。备忘录法和自底向上法是实现这一目标的两种不同路径其背后的设计哲学和思考起点截然不同。2.1 备忘录法带着地图的深度探险者备忘录法本质上是递归缓存。它的思考过程是最符合人类直觉的我们想要解决一个大问题比如爬到第n级台阶有多少种方法就直接去思考这个大问题。要解f(n)我需要知道f(n-1)和f(n-2)那我就递归地去调用f(n-1)和f(n-2)。如果不加任何优化这个递归树会指数级爆炸因为f(n-1)计算时会再算f(n-2)而f(n-2)在之前已经被计算过了。备忘录的引入就是给这次探险配了一张地图。我们初始化一个数组memo全部填上-1表示未计算。每次进入递归函数dfs(n)时先查地图如果memo[n] ! -1说明这个位置我已经来过了答案已知直接返回。否则我才真正去计算它计算完成后把结果memo[n]然后返回。这样每个子问题只会被计算一次。它的核心优势在于“按需计算”。我们只计算那些为了得到最终答案所必须计算的子问题。对于某些状态空间很大、但实际可达状态不多的题目比如一些游戏状态DP备忘录法可以避免初始化并计算整个庞大的DP表节省空间和时间。它的代码结构几乎就是递归的翻版对初学者理解“状态转移”非常友好。注意备忘录法虽然直观但它依然有递归的开销——函数调用栈。当递归深度很大时比如n10000可能会导致栈溢出错误。这是它相对于自底向上法的一个潜在缺点。2.2 自底向上法步步为营的建筑师自底向上法则是纯粹的迭代法。它完全摒弃了递归的“顶层思考”转而从最基础、最小的子问题开始。就像一个建筑师他不先想屋顶怎么盖而是先打好地基基础状态然后根据严格的图纸状态转移方程一层一层地向上建造。我们首先定义好DP数组dp[]的含义例如dp[i]表示到达第i级台阶的方法数。然后确定基础情况dp[0] 1起点算一种方法dp[1] 1。接着就是那个经典的循环for i in range(2, n1): dp[i] dp[i-1] dp[i-2]。我们从i2开始因为i0和i1我们已经知道了。这样当我们计算dp[i]时它所依赖的dp[i-1]和dp[i-2]一定已经在之前的迭代中计算并存储好了。它的核心优势在于“顺序确定无递归开销”。由于是顺序迭代我们很容易进行空间优化例如滚动数组也完全不用担心栈溢出。它强迫你将所有状态清晰地定义出来思维更严谨。绝大多数动态规划教程和面试解答默认采用的都是这种方法。那么如何选择这里有一个简单的决策流如果你的问题状态转移关系非常直观且状态空间是连续、完整的比如线性、矩阵优先用自底向上法它更高效、更标准。如果你的问题状态定义复杂或者存在大量无效状态计算时才会发现或者你首先想到的是递归解法那么备忘录法是一个极佳的优化起点它能帮你快速得到一个正确解之后再考虑能否转化为迭代。3. 经典案例实战从斐波那契到背包问题理论说再多不如代码跑一遍。我们通过三个经典问题来对比这两种方法的实现和细微差别。3.1 斐波那契数列入门第一课问题求第n个斐波那契数F(0)0, F(1)1, F(n)F(n-1)F(n-2)。备忘录法实现def fib_memo(n): memo [-1] * (n 1) # 初始化备忘录 def dfs(i): if i 1: return i if memo[i] ! -1: # 查备忘录 return memo[i] memo[i] dfs(i-1) dfs(i-2) # 计算结果并存入 return memo[i] return dfs(n)自底向上法实现def fib_dp(n): if n 1: return n dp [0] * (n 1) dp[0], dp[1] 0, 1 # 基础状态 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] # 状态转移 return dp[n]自底向上法空间优化版def fib_dp_opt(n): if n 1: return n prev, curr 0, 1 # 只保留前两个状态 for i in range(2, n 1): prev, curr curr, prev curr return curr对比分析备忘录法的dfs函数调用树会被大量剪枝每个i只计算一次时间复杂度O(n)。但它需要O(n)的栈空间递归深度和O(n)的备忘录空间。经典自底向上法时间复杂度O(n)空间复杂度O(n)。优化版自底向上法时间复杂度O(n)空间复杂度O(1)。这是最优解。实操心得斐波那契问题清晰地展示了自底向上法在空间优化上的巨大优势。一旦你发现状态转移只依赖于前几个固定状态立刻想到“滚动数组”或变量交替。3.2 最长上升子序列一维状态的延伸问题给定一个整数数组nums找到其中最长严格递增子序列的长度。状态定义dp[i]表示以第i个数字结尾的最长上升子序列的长度。注意这个定义是关键它确保了子序列的连续性。备忘录法实现思路 计算dfs(i)即以nums[i]结尾的LIS长度。我们需要遍历i之前的所有位置j如果nums[j] nums[i]那么nums[i]可以接在nums[j]形成的子序列后面状态转移为dfs(i) max(dfs(i), dfs(j) 1)。同样用memo数组存储dfs(i)的结果。自底向上法实现def lengthOfLIS(nums): if not nums: return 0 n len(nums) dp [1] * n # 每个元素本身至少是一个长度为1的LIS for i in range(n): # 计算每个dp[i] for j in range(i): # 遍历i前面的所有元素 if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) # 状态转移 return max(dp) # 答案不是dp[n-1]而是dp数组中的最大值复杂度分析时间复杂度O(n²)空间复杂度O(n)。优化技巧贪心二分查找 这不是备忘录或自底向上的直接优化而是利用了LIS问题的特殊性质。我们维护一个数组tails其中tails[k]存储长度为k1的上升子序列的最小可能末尾值。遍历nums用二分查找将当前数放入tails合适的位置。最终tails的长度就是答案。此法可将复杂度降至O(n log n)。def lengthOfLIS_opt(nums): tails [] for num in nums: # 在tails中寻找第一个大于等于num的位置 l, r 0, len(tails) while l r: mid (l r) // 2 if tails[mid] num: l mid 1 else: r mid if l len(tails): tails.append(num) # 比所有末尾都大延长子序列 else: tails[l] num # 替换使得该长度的子序列末尾更小 return len(tails)注意事项二分查找优化是LIS问题的经典技巧但它改变了DP的定义属于“另辟蹊径”。在面试中先给出O(n²)的标准DP解并分析复杂度再提出可以优化到O(n log n)会是非常加分的表现。3.3 01背包问题二维状态的典范问题有N件物品和一个容量为C的背包。第i件物品重量是w[i]价值是v[i]。求解将哪些物品装入背包可使总价值最大且不超过背包容量。状态定义dp[i][j]表示考虑前i件物品物品编号从1开始在背包容量为j的情况下能获得的最大价值。自底向上法实现标准版def knapsack_01(N, C, w, v): # 初始化dp数组多一行一列用于边界处理 dp [[0] * (C 1) for _ in range(N 1)] for i in range(1, N 1): # 遍历物品 for j in range(C 1): # 遍历容量 if j w[i-1]: # 当前容量装不下第i件物品注意索引 dp[i][j] dp[i-1][j] # 继承不放这件物品的状态 else: # 选择不放 或 放 dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i-1]] v[i-1]) return dp[N][C]状态转移方程解读dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])。这个方程是01背包的灵魂。它意味着对于第i件物品我们有两种选择不拿它那么价值就是前i-1件物品在容量j下的最优解dp[i-1][j]拿它那么就要在前i-1件物品中为它腾出w[i]的重量即dp[i-1][j - w[i]]然后加上它的价值v[i]。两者取最大值。空间优化滚动数组观察状态转移方程dp[i][...]只依赖于dp[i-1][...]。因此我们可以只用两行数组甚至一行数组。def knapsack_01_opt(N, C, w, v): dp [0] * (C 1) # 一维数组dp[j]表示容量为j时的最大价值 for i in range(N): # 遍历物品 # 必须逆序遍历容量这是关键。 for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[C]为什么必须逆序因为dp[j]依赖于上一轮考虑前i-1个物品时的dp[j - w[i]]。如果正序遍历当更新dp[j]时dp[j - w[i]]可能已经在同一轮考虑第i个物品时被更新过了这就相当于第i件物品被重复放入变成了“完全背包”问题。逆序保证了在更新dp[j]时dp[j - w[i]]还是上一轮的状态。备忘录法实现思路 定义递归函数dfs(i, j)表示考虑前i件物品剩余容量为j时的最大价值。用二维数组memo[i][j]记录结果。递归边界是i0没有物品或j0没有容量返回0。递归过程同样判断当前物品能否放入并取max(dfs(i-1, j), dfs(i-1, j-w[i])v[i])。备忘录法在这里写起来更直观但递归深度可能达到O(NC)对于大规模数据可能栈溢出。踩坑记录01背包的空间优化写法中内层循环逆序是一个必须刻在脑子里的点。我见过太多人在这里犯错导致程序逻辑完全错误。正序是“完全背包”逆序才是“01背包”。4. 优化技巧深度剖析时间与空间的博弈掌握了两种基本方法我们来看看如何让它们跑得更快、更省内存。这些技巧是区分普通解法和优秀解法的关键。4.1 状态定义的艺术如何设计高效的DP数组状态定义是动态规划的灵魂直接决定了转移方程的复杂度和空间开销。维度选择能用一维数组绝不用二维。例如在路径问题中如果只能向右和向下那么到达(i, j)点的路径数dp[i][j]可以只依赖于上一行和左侧有时可以用滚动数组优化为一维。状态含义有时改变状态含义能极大简化问题。比如在“买卖股票”系列问题中定义dp[i][0]表示第i天结束时持有股票的最大利润dp[i][1]表示第i天结束时不持有股票的最大利润比定义成“第i天买入/卖出”要清晰得多。偏移处理当状态值可能为负数时如一些带负权值的问题可以将整个状态值加上一个偏移量使其索引为正。例如如果状态范围在[-100, 100]我们可以定义数组大小为201索引时用状态值100。4.2 空间优化利器滚动数组与状态压缩这是自底向上法的核心优化手段。滚动数组当状态转移只依赖于固定的前几行或前几列时可以只保留这些行循环使用。最常见的是dp[i][...]只依赖于dp[i-1][...]那么只需一个dp[2][...]的数组用i % 2来切换当前行和上一行。更进一步的如01背包优化到一维数组。状态压缩当状态可以用二进制位表示时如旅行商问题TSP中“访问过哪些城市”的状态可以用一个整数的二进制位来表示集合将二维甚至多维DP压缩成一维。例如mask 5二进制101表示城市0和城市2已访问。这能将指数级状态空间用位运算高效处理。4.3 剪枝与提前终止减少无效计算在备忘录法和某些自底向上法中可以通过判断提前跳过无效状态。可行性剪枝在背包问题中如果当前剩余容量已经小于最小物品重量可以直接终止循环。最优性剪枝在某些搜索类DP如记忆化搜索中如果当前路径的“预估最优值”已经比已知答案差可以立即返回。初始化优化合理设置DP数组的初始值。有时将数组初始化为一个“不可能值”如-INF可以简化边界条件判断。在求最大值问题时常初始化为0或-INF在求最小值问题时常初始化为INF。4.4 遍历顺序的奥秘拓扑序与依赖关系自底向上法的循环顺序不是随意的它必须满足状态依赖的拓扑序。即在计算dp[i]时它所依赖的所有状态dp[k]k i都必须已经计算完成。线性DP通常顺序遍历即可。区间DP通常先遍历区间长度len再遍历起点l终点r l len - 1。这样保证在计算大区间时它依赖的小区间都已算好。背包问题01背包内层容量逆序完全背包内层容量正序这是由物品能否重复选取决定的。DAG上的DP有时需要先对图进行拓扑排序然后按照拓扑序进行状态转移。5. 从备忘录到自底向上思维转换与代码重构很多同学觉得备忘录法好想但自底向上法难写。其实它们是一个硬币的两面可以相互转化。转换步骤写出备忘录法的递归函数明确函数签名dfs(state)定义清楚状态参数和返回值。确定DP数组递归函数的参数组合就是DP数组的维度。dfs(i, j)对应dp[i][j]。递归函数的返回值就是dp[i][j]要存储的值。找出基础状态对应递归的终止条件base case。把这些情况下的dp值直接填好。确定遍历顺序分析递归函数中dfs(state)调用了哪些dfs(next_state)。next_state就是state所依赖的状态。在自底向上中你必须保证在计算dp[state]时所有dp[next_state]都已经计算好了。这通常意味着你需要按照某种拓扑序来遍历状态。写出状态转移方程递归函数体内的计算逻辑就是状态转移方程。把dfs调用换成dp数组的访问即可。举例爬楼梯问题每次可爬1或2级备忘录法def dfs(n): if n2:return 1; if memo[n]!-1:return memo[n]; memo[n]dfs(n-1)dfs(n-2); return memo[n]转换DP数组一维dp[n1]。基础状态dp[0]1, dp[1]1。从0级到0级有1种方法不动遍历顺序dfs(n)依赖dfs(n-1)和dfs(n-2)即大n依赖小n。所以从i2遍历到n。状态转移dp[i] dp[i-1] dp[i-2]。个人体会我强烈建议在初学某个新型DP问题时先尝试用备忘录法写出一个正确的解。这能帮你理清状态和转移。一旦备忘录法通过再着手将其转化为自底向上法。这个过程能极大地加深你对问题状态之间依赖关系的理解。久而久之你看到问题就能直接构思出自底向上的解法了。6. 常见陷阱与调试技巧动态规划的bug往往比普通算法更难查因为状态是层层递推的一个地方出错后面全盘皆错。陷阱1初始化错误现象结果比预期小或者出现负数等异常值。检查仔细检查dp数组的初始值。求最大值时是否该初始化的地方初始化为0了是否有些状态根本不可能达到需要初始化为-inf边界情况如索引为0是否处理正确陷阱2遍历顺序错误现象结果不正确尤其是涉及多维状态或依赖关系复杂时。检查画一个小的状态依赖图。确认你循环的i,j顺序是否保证了在计算dp[i][j]时它所需要的dp[i-1][j]、dp[i][j-1]等状态都已经计算完毕在背包问题中检查容量循环是正序还是逆序。陷阱3状态转移方程遗漏情况现象结果对一部分测试用例正确对另一部分错误。检查重新推导状态转移方程。考虑所有可能的“选择”。在背包问题中是“放”与“不放”在字符串编辑距离中是“增、删、改、不变”。确保你的max或min操作涵盖了所有可能性。陷阱4数组越界现象运行时出现索引错误。检查特别是在状态转移中访问dp[i-1][j-w]这类索引时确保j-w大于等于0。在初始化dp数组时维度是否足够大通常是n1。调试技巧打印DP表这是最有效的方法。在关键循环结束后将整个dp数组打印出来。与手动计算的小规模样例的DP表进行对比不一致的地方就是bug所在。缩小输入用一个非常小的、可以手动计算的输入比如n3,4来测试你的程序。对比你的程序输出和手算结果。橡皮鸭调试法向别人或者一只橡皮鸭一行一行解释你的代码特别是状态定义和转移方程。在解释的过程中你经常能自己发现逻辑漏洞。单元测试针对不同的边界条件空数组、单个元素、最大值、最小值编写测试用例。7. 复杂场景应用与思维拓展掌握了基础模型和优化技巧后动态规划可以应用于更复杂的场景这往往需要你将实际问题巧妙地映射到已知模型或者组合多种技巧。场景1带维度增加的DP例如“股票买卖”问题状态中需要增加一个维度来表示当前是否持有股票、以及交易次数。dp[i][k][0/1]表示第i天最多进行了k次交易手上不持有/持有股票的最大利润。状态转移方程需要同时考虑天数的推移和交易动作。场景2区间DP用于解决涉及区间性质的问题如石子合并、最长回文子串。核心是定义dp[l][r]表示区间[l, r]上的最优解然后枚举区间分割点k状态转移通常形如dp[l][r] min/max(dp[l][k] dp[k1][r] cost(l, r, k))。遍历顺序必须是先小区间后大区间。场景3树形DP当问题结构是一棵树时如公司派对、二叉树抢劫需要在树上进行状态转移。通常采用后序遍历深度优先搜索在递归返回时将子节点的状态信息汇总到父节点。状态定义往往与节点是否被选中有关如dp[node][0]表示不选node节点的最优解dp[node][1]表示选中的最优解。场景4状态机DP有些问题可以抽象成在一个状态机中转移。例如“买卖股票含冷冻期”问题可以定义三个状态dp[i][0]持有股票dp[i][1]不持有股票且在冷冻期dp[i][2]不持有股票且不在冷冻期。然后清晰地画出状态之间的转移关系图再写出转移方程。思维拓展何时想到用DP我个人的经验是当问题满足以下一个或多个特征时可以优先考虑DP求最值最大值、最小值、最长、最短等。计数问题有多少种方法、多少种方案。可行性问题是否存在某种方案。问题可以分解大问题的最优解包含子问题的最优解最优子结构。子问题重叠在递归求解过程中相同的子问题被反复计算。最后再分享一个我自己的学习心得动态规划的功力经典模型熟练度 问题抽象能力 大量练习。先把“斐波那契”、“爬楼梯”、“01背包”、“完全背包”、“最长公共子序列”、“最长上升子序列”、“编辑距离”这几个最经典的模型练到肌肉记忆。然后遇到新问题时努力去联想它和哪个经典模型相似或者如何通过增加状态维度来转化为经典模型。这个过程没有捷径刷题量上去后那种“这道题一看就是DP”的直觉自然就来了。