1. 从“暴力穷举”到“聪明记忆”动态规划的核心思想如果你刷过一些算法题或者准备过技术面试那么“动态规划”这四个字大概率是你绕不开的一座大山。很多人第一次接触它感觉就像在看天书状态转移方程、最优子结构、重叠子问题……一堆术语砸下来还没开始解题头已经大了。更让人沮丧的是看答案时觉得“哦原来如此简单”自己动手时却完全不知道从何下手状态都定义不出来。我自己在初学动态规划时也经历过这个阶段。后来在大量的项目实战和面试辅导中我逐渐意识到动态规划之所以难不是因为它本身复杂而是因为大多数教程把它讲复杂了。它本质上是一种用“空间换时间”的编程思想核心目的就一个避免重复计算。我们可以从一个最经典的例子——斐波那契数列——来直观感受一下。斐波那契数列的定义是F(0)0 F(1)1 F(n)F(n-1)F(n-2) (n2)。如果让你写一个函数计算 F(20)最直观的写法就是递归def fib(n): if n 1: return n return fib(n-1) fib(n-2)这个代码简洁明了但效率极其低下。如果你画出fib(5)的递归树你会发现fib(3)被计算了两次fib(2)被计算了三次。随着 n 增大这种重复计算是指数级增长的。计算fib(40)可能就需要好几秒甚至更久。这就是典型的“重叠子问题”在求解大问题的过程中许多更小的子问题被反复计算。动态规划的第一招就是“记忆化搜索”Memoization。我们开一个数组或者字典memo在计算fib(n)之前先查一下memo[n]有没有值。如果有直接返回如果没有再计算并把结果存进memo。这样每个子问题只会被计算一次。def fib_memo(n, memo{}): if n 1: return n if n not in memo: memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n]这已经是一种动态规划了自顶向下。但更常见的动态规划是“自底向上”的迭代写法。我们直接从最小的子问题开始算起逐步构建出大问题的解。def fib_dp(n): if n 1: return n # dp[i] 表示斐波那契数列第 i 项的值 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]这个dp数组就是我们“购买”的空间用它存储了所有子问题的解从而避免了重复计算。dp[i] dp[i-1] dp[i-2]这个式子就是状态转移方程它描述了问题状态之间是如何演进的。所以动态规划不是什么魔法。当你发现一个问题可以被分解成重叠的子问题并且子问题的最优解能构成原问题的最优解最优子结构时你就可以尝试用动态规划。它的思考过程可以概括为定义状态 - 建立状态转移方程 - 确定初始边界条件 - 计算顺序自底向上- 输出答案。接下来我会用几个从易到难的案例带你完整走一遍这个流程并分享一些我踩过的坑和总结的技巧。2. 入门案例拆解从“爬楼梯”到“零钱兑换”我们先从两个面试高频题入手把动态规划的基本流程走通。你会发现它们的套路是高度一致的。2.1 爬楼梯问题理解状态定义问题描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶这是最经典的入门题。我们一步步分析定义状态这是最关键的一步状态定义得好问题就解决了一半。我们要问自己什么信息能唯一描述当前所处的“局面”在这里“局面”就是你爬到了第几阶以及到达这一阶有多少种方法。所以我们定义dp[i]为爬到第 i 阶楼梯共有多少种不同的方法。这就是我们的“状态”。建立状态转移方程思考如何从已知的小状态推导出未知的大状态。要爬到第 i 阶最后一步只能从第 i-1 阶爬1步上来或者从第 i-2 阶爬2步上来。既然到达 i-1 阶有dp[i-1]种方法到达 i-2 阶有dp[i-2]种方法并且这些方法互不重复因为最后一步不同那么到达第 i 阶的方法总数就是这两者之和。所以方程是dp[i] dp[i-1] dp[i-2]。确定初始条件方程需要基础才能启动。dp[1]是多少爬到第1阶只有一种方法爬1步。dp[2]呢有两种一次爬2步或者分两次各爬1步。所以dp[1]1, dp[2]2。注意这里为了方便理解我们让i从1开始。更常见的写法是定义dp[0]1“爬到第0阶”有一种方法不动这样dp[1]1, dp[2]2也能通过dp[2]dp[1]dp[0]推导出来。计算顺序与实现显然我们需要从i3开始一直计算到in。因为计算dp[i]需要先知道dp[i-1]和dp[i-2]。def climbStairs(n): if n 2: return n dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]空间优化观察状态转移方程dp[i]只依赖于前两个状态dp[i-1]和dp[i-2]。我们完全没必要维护整个 O(n) 的数组只用两个变量滚动更新即可将空间复杂度降至 O(1)。def climbStairs_opt(n): if n 2: return n prev, curr 1, 2 # prev 代表 dp[i-2], curr 代表 dp[i-1] for i in range(3, n 1): # 计算新的 dp[i] new prev curr # 滚动更新变量为下一轮做准备 prev, curr curr, new return curr # 循环结束时curr 就是 dp[n]踩坑心得很多新手在这里会纠结dp[0]到底该不该等于1。我的建议是优先从有实际意义的、最小的子问题开始初始化。比如这里从dp[1]和dp[2]开始定义逻辑更直观不易出错。如果为了公式统一非要定义dp[0]1一定要在注释里写明其物理意义“不爬”作为一种方案否则过段时间自己都看不懂。2.2 零钱兑换问题理解“选择”与“最值”问题描述给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。你可以认为每种硬币的数量是无限的。这个问题和爬楼梯神似但加入了“选择”和“求最小值”的概念。我们依然套用流程定义状态dp[i]表示凑出总金额i所需的最少硬币个数。建立状态转移方程如何凑出金额i假设最后一枚硬币的面额是coin那么在这枚硬币之前我们已经凑出了金额i - coin并且使用了dp[i - coin]枚硬币。由于我们要找最少的硬币数所以我们需要遍历所有可能的coin前提是coin i选择那个能使dp[i - coin] 1最小的方案。因此方程是dp[i] min(dp[i - coin] 1) for coin in coins if coin i。确定初始条件dp[0] 0凑出金额0需要0枚硬币。这是一个合法的、有明确意义的边界状态。对于其他dp[i]我们初始化为一个很大的数比如amount 1或float(inf)表示“暂时无法凑出”。计算顺序与实现我们需要从i1计算到iamount。对于每个i遍历所有硬币面额。def coinChange(coins, amount): # 初始化 dp 数组dp[i] 表示凑出金额 i 的最小硬币数 # 初始化为一个不可能的大值这里用 amount 1因为最多用 amount 个1元硬币 dp [amount 1] * (amount 1) dp[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) # 如果 dp[amount] 没有被更新过说明无法凑出 return dp[amount] if dp[amount] amount else -1为什么初始化为amount 1因为最坏情况是用amount个1元硬币如果存在1元硬币。amount 1是一个有效的“无穷大”标识最后通过比较dp[amount] amount来判断是否无解。实操技巧在解决求最值最小/最大的动态规划问题时初始化是一个关键。通常做法是求最小值初始化为一个很大的正数如float(inf)或amount1。求最大值初始化为一个很小的数如float(-inf)或0具体看情况。求方案数通常初始化为0但dp[0]往往初始化为1代表一种初始方案。 务必根据问题的物理意义仔细设定dp[0]这是整个递推的基石。3. 二维动态规划进阶在字符串与矩阵中穿梭当状态由一个变量无法描述时我们就需要升维使用二维甚至更高维的dp数组。字符串匹配和矩阵路径是两类典型问题。3.1 最长公共子序列经典的双序列匹配模型问题描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列LCS的长度。子序列是指在不改变字符相对顺序的情况下删除某些字符也可以不删除后形成的新字符串。例如text1 abcde,text2 aceLCS 是ace长度为3。定义状态我们需要同时考虑两个字符串的进度。定义dp[i][j]为text1的前i个字符和**text2的前j个字符**的最长公共子序列长度。这里“前 i 个”通常指下标从0到 i-1 的子串。这种定义方式非常普遍。建立状态转移方程我们比较text1[i-1]和text2[j-1]因为下标从0开始。如果它们相等那么这个字符一定在LCS中。dp[i][j] dp[i-1][j-1] 1。如果它们不相等那么这个字符不可能同时出现在LCS中。LCS的长度要么来自text1的前 i-1 个和text2的前 j 个dp[i-1][j]要么来自text1的前 i 个和text2的前 j-1 个dp[i][j-1]。我们取最大值dp[i][j] max(dp[i-1][j], dp[i][j-1])。确定初始条件当其中一个字符串为空时LCS长度为0。即dp[0][j] 0对所有 j以及dp[i][0] 0对所有 i。计算顺序与实现我们需要一个双重循环i从 1 到len(text1)j从 1 到len(text2)。计算dp[i][j]需要其左方、上方、左上方三个状态这个计算顺序从左到右从上到下是满足的。def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) # 创建 (m1) x (n1) 的二维数组多出来的一行一列用于表示空串 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] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) return dp[m][n]如何输出具体的LCS字符串上述代码只返回了长度。要输出序列我们需要在填表的同时记录状态转移的方向然后从dp[m][n]反向回溯。这是一个常见的 follow-up 问题。经验之谈二维DP的索引设计是个易错点。dp[i][j]对应text1[0..i-1]和text2[0..j-1]这样dp[0][*]和dp[*][0]就自然地代表了空串简化了边界处理。我强烈建议统一使用这种“长度1”的定义方式它比直接使用字符串下标dp[i][j]对应text1[0..i]和text2[0..j]更不容易出错因为后者需要单独初始化第一行和第一列。3.2 最小路径和在网格中做决策问题描述给定一个包含非负整数的m x n网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。每次只能向下或者向右移动一步。定义状态dp[i][j]表示从左上角(0, 0)走到位置(i, j)的最小路径和。建立状态转移方程要走到(i, j)上一步只能来自其上方(i-1, j)或者左方(i, j-1)。我们选择路径和更小的那条路过来再加上当前格子的值。因此dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。确定初始条件起点dp[0][0] grid[0][0]。第一行i0只能从左方来所以dp[0][j] dp[0][j-1] grid[0][j]。第一列j0只能从上方来所以dp[i][0] dp[i-1][0] grid[i][0]。计算顺序与实现双重循环遍历整个网格即可。由于计算dp[i][j]只需要其上方和左方的值我们也可以进行空间优化只维护一维数组。def minPathSum(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] # 初始化起点 dp[0][0] grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] # 填充其余部分 for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j] return dp[m-1][n-1]空间优化滚动数组def minPathSum_opt(grid): m, n len(grid), len(grid[0]) # 只维护一行数据 dp [0] * n dp[0] grid[0][0] # 初始化第一行 for j in range(1, n): dp[j] dp[j-1] grid[0][j] # 处理后续行 for i in range(1, m): # 每行的第一个元素只能从上方来 dp[0] dp[0] grid[i][0] for j in range(1, n): # dp[j] 在更新前代表上一行的 dp[i-1][j] # dp[j-1] 代表本行已经计算好的 dp[i][j-1] dp[j] min(dp[j], dp[j-1]) grid[i][j] return dp[n-1]优化后空间复杂度从 O(m*n) 降到了 O(n)。理解这个优化需要对dp数组在每一轮循环中的含义有清晰的认识。4. 背包问题精讲掌握动态规划的经典范式背包问题是动态规划领域的一座里程碑它抽象出了一大类“选择-容量-价值”的优化问题。彻底理解背包问题很多其他问题都能迎刃而解。4.1 0-1背包问题每个物品只能选一次问题描述有N件物品和一个容量为W的背包。第i件物品的重量是weight[i]价值是value[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量且总价值最大。这是最基础的背包模型。关键在于每件物品只能选择0次不放入或 1次放入。定义状态dp[i][j]表示考虑前 i 件物品在背包容量为j的情况下可以装入的最大价值。建立状态转移方程对于第i件物品注意i从1开始计数对应weight[i-1]和value[i-1]我们有两种选择不放入背包那么最大价值就等于考虑前i-1件物品、容量为j时的最大价值即dp[i-1][j]。放入背包前提是j weight[i-1]那么最大价值等于“第i件物品的价值”加上“考虑前i-1件物品、剩余容量为j - weight[i-1]时的最大价值”即value[i-1] dp[i-1][j - weight[i-1]]。 我们要取这两种选择中的最大值。所以dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i-1]] value[i-1])其中后一项仅在j weight[i-1]时有效。确定初始条件当物品数量为0或背包容量为0时最大价值为0。即dp[0][j] 0,dp[i][0] 0。实现与空间优化def knapsack_01(W, weight, value): N len(weight) dp [[0] * (W 1) for _ in range(N 1)] for i in range(1, N 1): w_i, v_i weight[i-1], value[i-1] for j in range(1, W 1): # 默认不选第 i 件物品 dp[i][j] dp[i-1][j] # 如果背包容量够尝试选择第 i 件物品 if j w_i: dp[i][j] max(dp[i][j], dp[i-1][j - w_i] v_i) return dp[N][W]观察状态转移方程dp[i][j]只依赖于dp[i-1][...]即上一行的数据。因此我们可以将二维数组压缩成一维数组但需要逆序遍历背包容量j。def knapsack_01_opt(W, weight, value): N len(weight) dp [0] * (W 1) # dp[j] 表示容量为 j 的背包能装的最大价值 for i in range(N): w_i, v_i weight[i], value[i] # 必须逆序遍历保证 dp[j - w_i] 是上一轮i-1的结果 for j in range(W, w_i - 1, -1): dp[j] max(dp[j], dp[j - w_i] v_i) return dp[W]为什么必须逆序因为dp[j - w_i]需要是“未考虑当前物品i”时的值。如果正序遍历在计算dp[j]时dp[j - w_i]可能已经被本轮的更新覆盖了即已经考虑了物品i这就变成了“完全背包”问题物品可重复选取违反了0-1背包的规则。这是背包问题最核心的一个技巧务必理解。4.2 完全背包问题物品数量无限问题描述与0-1背包类似但每种物品有无限件。状态定义不变依然是dp[i][j]。状态转移方程需要改变因为物品i可以选0件、1件、2件……直到放不下。dp[i][j] max(dp[i-1][j], dp[i][j - weight[i-1]] value[i-1]) 其中后一项在j weight[i-1]时有效。注意第二个项是dp[i][j - w_i]而不是dp[i-1][j - w_i]。这是因为即使考虑了前i种物品我们仍然可以再次选择物品i。一维优化后的代码与0-1背包几乎一样唯一的区别就是内层循环正序遍历jdef knapsack_complete(W, weight, value): N len(weight) dp [0] * (W 1) for i in range(N): w_i, v_i weight[i], value[i] # 完全背包正序遍历 for j in range(w_i, W 1): dp[j] max(dp[j], dp[j - w_i] v_i) return dp[W]正序保证了dp[j - w_i]是已经考虑过当前物品i的结果从而实现了物品的无限次选取。核心对比记忆0-1背包一维数组优化内层容量循环逆序(for j in range(W, w_i-1, -1))。完全背包一维数组优化内层容量循环正序(for j in range(w_i, W1))。 这个区别源于状态转移方程中依赖的是上一行(i-1)还是本行(i)的数据。死记硬背容易忘理解其背后的“依赖关系”才是关键。5. 状态压缩与降维打击当空间成为瓶颈在动态规划中尤其是二维DP空间复杂度有时会成为问题比如网格非常大。状态压缩技巧或称滚动数组可以极大地节省空间。我们之前已经在“爬楼梯”和“最小路径和”中见过一维优化的例子。这里再深入探讨一个更复杂的案例买卖股票的最佳时机含冷冻期。问题描述给定一个整数数组prices其中第i个元素代表了第i天的股票价格。你可以尽可能地完成更多的交易多次买卖一支股票但卖出股票后你无法在第二天买入股票即冷冻期为1天。计算你所能获取的最大利润。这个问题有多个状态持有股票、不持有股票且处于冷冻期、不持有股票不处于冷冻期。一个直观的二维DP定义是dp[i][0]: 第i天结束时持有股票的最大利润。dp[i][1]: 第i天结束时不持有股票且处于冷冻期即第i天卖出了股票的最大利润。dp[i][2]: 第i天结束时不持有股票且不处于冷冻期的最大利润。状态转移方程如下dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])。今天持有股票要么是昨天就持有要么是昨天不持有且非冷冻期今天买入。dp[i][1] dp[i-1][0] prices[i]。今天处于冷冻期意味着今天卖出了股票所以利润是昨天持有的利润加上今天卖出的收入。dp[i][2] max(dp[i-1][1], dp[i-1][2])。今天不持有且非冷冻期要么昨天是冷冻期要么昨天也是非冷冻期。初始化dp[0][0] -prices[0]第一天买入dp[0][1] 0dp[0][2] 0。这个解法需要 O(n) 的空间n为天数。但观察方程dp[i]只依赖于dp[i-1]。因此我们可以只用三个变量来滚动更新。def maxProfit_with_cooldown(prices): if not prices: return 0 n len(prices) # 初始化第0天的状态 hold -prices[0] # dp[0][0] cold 0 # dp[0][1] not_hold 0 # dp[0][2] for i in range(1, n): # 计算第i天的新状态需要用到旧状态所以先存下来 pre_hold, pre_cold, pre_not_hold hold, cold, not_hold # 更新第i天的状态 hold max(pre_hold, pre_not_hold - prices[i]) cold pre_hold prices[i] not_hold max(pre_cold, pre_not_hold) # 最后一天持有股票肯定不是最优没卖掉所以取 cold 和 not_hold 的最大值 return max(cold, not_hold)这种优化将空间复杂度从 O(n) 降到了 O(1)。关键在于识别出状态转移只依赖于前一个时间步的状态并且注意在更新时由于变量会相互覆盖需要先用临时变量保存旧值。降维的通用思路当你发现dp[i][...]的状态只依赖于dp[i-1][...]或有限的前几个状态时就可以考虑用滚动数组。具体做法是分析状态转移方程确定依赖关系。如果只依赖上一行通常可以压缩到一维如0-1背包或几个变量如股票问题。如果依赖前两行可以压缩到两行交替使用。特别注意更新顺序在压缩到一维时逆序还是正序遍历容量/天数取决于依赖的是“旧状态”还是“可能被覆盖的新状态”。这是最容易出错的地方画个图模拟一下更新过程会很有帮助。6. 动态规划的“灵魂”如何识别与构造状态转移方程学了一堆例题但遇到新题还是不会这是常态。动态规划的难点不在于编码而在于“如何想到用DP”以及“如何定义状态和方程”。我总结了一套思考框架亲测有效。第一步判断问题是否具有“最优子结构”和“重叠子问题”。最优子结构一个问题的最优解包含其子问题的最优解。比如最短路径问题从A到C的最短路径如果经过B那么这条路径上从A到B、从B到C的段落也必定分别是A到B、B到C的最短路径。重叠子问题在递归求解时相同的子问题会被反复计算。可以通过画递归树或心算来感受。如果感觉“暴力搜索会做很多重复工作”那大概率可以用DP优化。第二步尝试定义状态。状态就是描述问题某个“局面”的一组参数。问自己需要哪些信息才能唯一确定当前所处的阶段并且能够向后续阶段推进单序列问题如最大子数组和通常状态定义为dp[i]表示以第i个元素结尾的某种性质。双序列问题如编辑距离、LCS通常状态定义为dp[i][j]表示涉及第一个序列的前i个和第二个序列的前j个。背包问题状态是dp[i][j]i表示物品范围j表示容量限制。区间问题如石子合并状态可能是dp[i][j]表示区间[i, j]上的最优解。状态机问题如股票买卖状态需要多个维度如dp[i][0/1/2]表示第i天处于不同状态持有、卖出、冷冻下的最优解。一个技巧先想想暴力递归怎么做。递归函数的参数通常就是状态变量。第三步推导状态转移方程。这是最核心的一步。思考如何从已知的、更小的状态计算出当前状态通常对应着在当前位置做一个“决策”。对于dp[i]看看它和dp[i-1]dp[i-2]... 有什么关系。决策点往往是“是否包含当前元素”、“从哪个前驱状态转移过来”。对于dp[i][j]看看它和dp[i-1][j]dp[i][j-1]dp[i-1][j-1]有什么关系。决策点往往是“两个序列的当前元素是否匹配”、“进行哪种操作增删改”。通用形式dp[新状态] BestChoice( dp[所有可能的前驱状态] 本次决策的代价/收益 )。这里的BestChoice可能是min,max,sum等。第四步确定边界条件Base Case。也就是最小的、不可再分的子问题的解。通常是状态索引为0或1时的值。一定要给这些初始状态赋予有实际意义的、正确的值这是递推的起点。第五步确定计算顺序。要保证在计算dp[当前状态]时它所依赖的所有子状态都已经被计算出来。对于一维DP通常是从左到右对于二维DP通常是从上到下、从左到右。有时也可能需要斜着遍历或者从后往前遍历。第六步实现并考虑优化。先写出清晰但可能费空间的版本比如完整的二维数组。确保正确后再考虑是否可以进行状态压缩滚动数组、空间优化等。7. 避坑指南与实战心得在多年的刷题和项目应用中我积累了一些动态规划中常见的“坑”希望能帮你少走弯路。坑一状态定义不当导致转移方程复杂或错误。这是最常见的问题。好的状态定义应该让转移方程简洁自然。如果发现方程写起来非常别扭或者需要很多if-else分支很可能状态定义需要调整。例如在“最长递增子序列”问题中定义dp[i]为“以nums[i]结尾的最长递增子序列长度”比定义为“前i个元素的最长递增子序列长度”要容易推导得多因为后者无法仅通过dp[i-1]确定dp[i]。坑二忽视边界条件或初始化错误。dp[0]、dp[0][0]这些初始值必须仔细推敲。例如在“不同路径”问题中dp[0][j]和dp[i][0]都应该初始化为1因为到第一行或第一列的任意格子都只有一条路径。如果初始化成0结果就全错了。一个检查方法是用最小的、能手动验证的实例比如2x2网格跑一遍你的DP初始化看结果是否正确。坑三遍历顺序错误导致依赖的子状态还未计算。尤其是在进行空间优化如一维数组时遍历顺序至关重要。0-1背包的内层逆序和完全背包的内层正序就是典型例子。我的建议是先写出二维的、逻辑清晰的版本然后像我们前面做的那样在纸上画出一维数组模拟更新过程来确定正确的遍历顺序。坑四混淆“子序列”和“子数组”。这是两个完全不同的概念。“子序列”可以不连续而“子数组”必须是连续的。它们对应的DP状态定义和转移方程天差地别。例如“最大子数组和”问题dp[i]定义必须以nums[i]结尾因为子数组要求连续而“最长递增子序列”问题dp[i]虽然也以nums[i]结尾但转移时需要遍历前面所有的j因为子序列不要求连续。坑五过度追求一维优化牺牲了代码可读性。在面试或项目初期正确性远比那一点空间优化重要。除非空间限制非常严格否则我建议先写出直观的二维DP代码确保逻辑正确、面试官能看懂。在解释清楚思路后如果时间允许再提一句“这个还可以用滚动数组优化到O(n)空间”。一上来就写优化后的代码容易把自己绕进去也容易让面试官困惑。实战心得从“记忆化搜索”入手如果你觉得直接想状态转移方程很困难可以尝试先写“记忆化搜索”Memoization也就是带缓存的递归。这更符合人类的自然思维自顶向下。写出递归函数后其参数就是状态递归调用就是状态转移。然后很容易就能改写成自底向上的迭代DP。这是一个非常有效的训练方法。最后动态规划是一种需要大量练习才能内化的思想。不要指望看几篇文章就能精通。我的建议是按照专题线性DP、区间DP、背包DP、状态机DP等集中刷题每做一题不仅写出代码更要能在白板上清晰地讲出状态定义、方程推导、边界条件和优化思路。当你拿到新题能下意识地开始“定义状态 - 找转移 - 定边界”时你就真正入门了。剩下的就是在不断的实践中积累更多模型和技巧让这种思维成为你的本能。
