1. 动态规划从“傻算”到“聪明算”的思维跃迁如果你刷过算法题或者准备过技术面试那么“动态规划”这四个字对你来说绝对是一个又爱又恨的存在。爱的是一旦掌握了它很多看似复杂的难题都能迎刃而解代码简洁优雅恨的是它的入门门槛似乎有点高状态转移方程、重叠子问题、最优子结构这些概念听起来就让人头大。很多人学动态规划就像在背公式题目稍微一变就无从下手。今天我们不谈那些枯燥的定义就从最朴素的想法出发聊聊动态规划到底是怎么一回事以及它赖以生存的两个核心基石——重叠子问题和最优子结构。理解了它们你才算真正摸到了动态规划的门道而不是仅仅在背模板。简单来说动态规划是一种“用空间换时间”的算法思想它通过把原问题分解为相对简单的子问题并存储子问题的解来避免重复计算从而高效地解决复杂问题。它特别适合解决那些具有“最优子结构”和“重叠子问题”性质的问题。听起来还是有点抽象别急我们用一个最经典的例子一步步把它掰开揉碎。2. 从斐波那契数列看透“重叠子问题”2.1 最直观的递归解法及其陷阱让我们从几乎所有人都见过的斐波那契数列Fibonacci Sequence开始。它的定义很简单F(0) 0, F(1) 1, F(n) F(n-1) F(n-2) (n 2)。比如数列的前几项是0, 1, 1, 2, 3, 5, 8, 13...如果让你写一个函数计算F(n)你的第一反应很可能是递归def fib_recursive(n): if n 1: return n return fib_recursive(n-1) fib_recursive(n-2)代码非常简洁完全符合数学定义。我们来计算一下fib_recursive(5)的过程。为了得到F(5)我们需要计算F(4)和F(3)为了得到F(4)需要计算F(3)和F(2)为了得到F(3)需要计算F(2)和F(1)…… 我们可以把这个计算过程画成一棵递归树F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ / \ F(2) F(1)F(1)F(0) / \ F(1) F(0)仔细观察这棵树你会发现一个严重的问题F(3)被计算了两次F(2)被计算了三次F(1)和F(0)被计算的次数更多。随着n的增大这种重复计算会呈指数级增长。计算F(20)时F(3)会被重复计算上千次这就是典型的“重叠子问题”在求解问题的过程中相同的子问题被反复计算多次。注意这里就是动态规划思想的第一个触发点。当你发现你的递归解法存在大量重复计算时就应该立刻想到是否可以用某种方式把这些子问题的解“存起来”避免重复劳动。2.2 引入“记忆化搜索”解决重叠子问题的初级方案既然问题是重复计算那么最直接的想法就是“记住”已经算过的结果。这种方法在算法中被称为“记忆化搜索”或“带备忘录的递归”。我们创建一个数组或字典memo在计算F(n)之前先查一下memo[n]有没有值如果有直接返回如果没有再计算并把结果存入memo再返回。def fib_memoization(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 1: memo[n] n else: memo[n] fib_memoization(n-1, memo) fib_memoization(n-2, memo) return memo[n]还是计算F(5)。这次当计算完F(3)后结果被保存在memo[3]中。之后无论哪条分支再需要F(3)都直接从备忘录中读取避免了重新展开递归树进行计算。这使得时间复杂度从恐怖的指数级O(2^n)降到了线性级O(n)因为每个子问题F(0)到F(n)都只被计算了一次。实操心得记忆化搜索是理解动态规划非常棒的桥梁。它本质上是一种“自顶向下”的动态规划。你写的还是递归函数但通过一个备忘录避免了重复。在面试或竞赛中如果一时想不出状态转移方程先写出一个暴力递归然后加上记忆化往往就能得到一个可接受的、高效的解法。2.3 递推解法标准的“自底向上”动态规划记忆化搜索是“自顶向下”的我们从目标F(n)出发逐步分解到基础情况。动态规划更常见的写法是“自底向上”的递推。我们直接从基础情况开始一步步推导到目标。定义状态dp[i]表示斐波那契数列第i项的值。确定初始状态边界条件dp[0] 0,dp[1] 1。状态转移方程dp[i] dp[i-1] dp[i-2] (i 2)。这个方程描述了状态之间是如何“转移”或“推导”的。计算顺序由于dp[i]依赖于dp[i-1]和dp[i-2]我们必须从i2开始从小到大依次计算。def fib_dp(n): if n 1: return n dp [0] * (n 1) # 创建DP数组多一位是为了方便dp[i]对应F(i) 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[5]时dp[3]和dp[2]早已计算好并被存储在表格中直接取用即可完美解决了重叠子问题。更进一步的空间优化观察状态转移方程dp[i] dp[i-1] dp[i-2]我们发现当前状态i只依赖于前两个状态i-1和i-2。这意味着我们不需要保存整个dp数组只需要用两个变量滚动记录前两个状态即可将空间复杂度从O(n)优化到O(1)。def fib_optimized(n): if n 1: return n prev, curr 0, 1 # prev F(0), curr F(1) for i in range(2, n 1): prev, curr curr, prev curr # 滚动更新 return curr提示这种空间优化技巧在动态规划中非常常见尤其是当状态转移只依赖于有限的几个前序状态时如前1个、前2个。在写出标准DP解法后一定要审视一下状态转移方程看是否有空间优化的可能。这不仅能提升代码效率在面试中也是重要的加分项。3. 最优子结构动态规划能够求解最优解的前提理解了重叠子问题我们解决了“计算效率”的问题。但动态规划更强大的地方在于求解“最优解”问题比如最短路径、最大利润、最长序列等。这就要求问题必须具备第二个关键性质最优子结构。3.1 什么是最优子结构最优子结构指的是一个问题的最优解包含其子问题的最优解。换句话说我们可以通过子问题的最优解来构造出原问题的最优解。这个概念有点绕我们用一个更生活化的例子来解释假设你要从北京开车到上海并且想找一条最短的路线。如果这个问题具有最优子结构那么意味着从北京到上海的最短路线一定是由从北京到某个中间城市比如济南的最短路线加上从济南到上海的最短路线组成的。如果从北京到济南你走的不是最短路线那么拼出来的北京-上海路线也必然不是最短的。3.2 经典案例剖析凑零钱问题LeetCode上经典的“322. 零钱兑换”问题完美诠释了最优子结构。问题描述给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。你可以认为每种硬币的数量是无限的。为什么它能用动态规划假设amount 11,coins [1, 2, 5]。我们定义dp[i]为凑出金额i所需的最少硬币数量。我们想知道dp[11]原问题的最优解。考虑最后一步凑出11元最后一枚硬币可能是1元、2元或5元。如果最后一枚是1元那么剩下的11-110元需要以最优方式凑出即需要dp[10]枚硬币。那么总硬币数为dp[10] 1。如果最后一枚是2元总硬币数为dp[9] 1。如果最后一枚是5元总硬币数为dp[6] 1。dp[11]应该是这三种可能中的最小值min(dp[10]1, dp[9]1, dp[6]1)。这里的关键在于为了求dp[11]我们需要知道dp[10]、dp[9]、dp[6]这些子问题的最优解。并且dp[11]这个原问题的最优解确实是由这些子问题的最优解dp[10]等推导出来的。这就是“最优子结构”。状态转移方程dp[i] min(dp[i - coin] 1 for coin in coins if i - coin 0)初始状态dp[0] 0凑出0元需要0枚硬币其他dp[i]初始化为一个很大的数比如amount 1表示暂时不可达。def coinChange(coins, amount): # 初始化dp数组dp[i]表示金额i的最小硬币数初始化为一个不可能的大数 dp [amount 1] * (amount 1) dp[0] 0 # 边界条件 # 遍历所有金额状态从1到amount for i in range(1, amount 1): # 遍历所有硬币选择 for coin in coins: if i - coin 0: # 确保减去硬币面值后不会变成负数 # 状态转移尝试用这枚硬币看是否能得到更优解 dp[i] min(dp[i], dp[i - coin] 1) # 如果dp[amount]没有被更新过说明无法凑出 return dp[amount] if dp[amount] ! amount 1 else -1常见问题与排查问题为什么dp数组要初始化为amount 1解答因为最多的情况就是用amount个1元硬币来凑所以amount 1是一个有效的“无穷大”标识比任何可能的解都大。最后通过判断dp[amount]是否等于这个值来判断是否无解。问题双重循环的顺序能换吗先遍历硬币还是先遍历金额解答在这个问题中必须外层遍历金额内层遍历硬币。因为我们的状态dp[i]表示的是对于固定金额i考虑所有硬币选择后的最优解。如果外层遍历硬币就变成了另一种思路完全背包问题的排列数/组合数问题求出的就不是本题要求的最小硬币数了。这是动态规划中“遍历顺序”的关键点顺序错了结果就错了。3.3 不具备最优子结构的反例并非所有求最优解的问题都有最优子结构。一个著名的反例是“无权图的最长简单路径”问题。假设我们要求图中从A点到D点的最长简单路径不重复经过节点。B / \ A D \ / C路径 A-B-D 长度为2路径 A-C-D 长度也为2。但是A到D的最长路径可能是 A-B-C-D 长度为3。你会发现A-B-C-D 这条整体最优路径并不是由 A-B最优子路径和 B-C-D最优子路径组成的因为A-B只是A到B的一条边而B-C-D也不是B到D的最长路径B-D更长。子问题A到B的最长路径、B到D的最长路径的最优解无法合并成原问题A到D的最长路径的最优解。因此最长简单路径问题不具备最优子结构不能用动态规划高效求解实际上它是NP-Hard问题。4. 动态规划的通用解题框架与思维模式通过上面的例子我们可以总结出一套解决动态规划问题的通用思维框架。这套框架能帮你面对新问题时一步步理清思路。4.1 五步法拆解动态规划问题第一步定义状态最重要也是最难的一步状态就是描述问题局面的一组变量。定义的状态要能唯一确定一个子问题并且要能通过状态转移方程向其他状态迁移。对于斐波那契数列状态就是idp[i]表示第i项的值。对于凑零钱问题状态就是当前要凑的金额idp[i]表示凑出金额i的最少硬币数。对于经典的最长上升子序列LIS问题状态通常是以第 i 个数字结尾的最长上升子序列的长度记为dp[i]。对于01背包问题状态通常是二维的dp[i][w]表示考虑前i件物品在背包容量为w的情况下能获得的最大价值。第二步确定状态转移方程核心推导找出状态之间的关系即如何从已知的小状态推导出未知的大状态。这是动态规划的灵魂。斐波那契dp[i] dp[i-1] dp[i-2]凑零钱dp[i] min(dp[i - coin] 1)for coin in coinsLISdp[i] max(dp[j] 1)for allj iandnums[j] nums[i]01背包dp[i][w] max(dp[i-1][w], dp[i-1][w - weight[i]] value[i])(如果放得下)第三步确定初始状态边界条件也就是最小的、不可再分的子问题的解。这是递推的起点。斐波那契dp[0]0, dp[1]1凑零钱dp[0]0LIS每个dp[i]至少为1自身构成序列。01背包dp[0][...] 0考虑0件物品价值为0dp[...][0] 0容量为0价值为0。第四步确定计算顺序确保在计算当前状态时它所依赖的子状态已经被计算出来。斐波那契、凑零钱、LIS通常是从小到大遍历。01背包外层遍历物品i内层遍历容量w。注意内层遍历容量时如果是01背包每件物品最多选一次需要从大到小遍历以避免物品被重复选取如果是完全背包物品无限则需要从小到大遍历。第五步优化空间可选但重要分析状态转移方程看是否能用更小的空间来存储状态例如用滚动数组或几个变量。4.2 思维模式如何想到用动态规划当你遇到一个新问题时可以问自己以下几个问题问题是否在求一个最优解最大值、最小值、最长、最短等如果是动态规划是一个候选。问题能否被分解为规模更小的相似子问题尝试思考要解决原问题是否需要先解决几个更小的、模式相同的问题这些子问题是否相互重叠即解决大问题时是否会反复遇到相同的小问题如果是记忆化/动态规划可以避免重复计算。子问题的最优解能构成原问题的最优解吗即是否满足“最优子结构”这是动态规划有效的关键。以“爬楼梯”问题为例每次可以爬1或2级台阶到第n级有多少种方法求方案数可以看作一种“计数”最优解。想到达第n级最后一步要么从第n-1级跨1步要么从第n-2级跨2步。所以ways(n)依赖于ways(n-1)和ways(n-2)。问题被分解了。计算ways(n-1)时又会用到ways(n-2)和ways(n-3)显然ways(n-2)被重复计算了。存在重叠子问题。到达第n级的总方法数确实等于从n-1级上来的方法数加上从n-2级上来的方法数。最优子结构成立。 结论这是一个斐波那契数列问题的变种可以用动态规划完美解决。5. 经典问题深度实战01背包与最长上升子序列掌握了框架我们用它来解剖两个更复杂、面试频率极高的经典问题。5.1 01背包问题二维状态与空间优化问题描述有N件物品和一个容量为W的背包。第i件物品的重量是weight[i]价值是value[i]。每件物品只能选择一次0或1求解将哪些物品装入背包可使总价值最大。第一步定义状态这是最核心的一步。我们必须用状态描述出“当前决策到了哪一步”以及“当前的背包容量”。因此定义一个二维数组dp[i][w]。i代表我们只考虑前i件物品物品编号从1到N。w代表当前背包的剩余容量实际编程中常表示容量上限。dp[i][w]表示考虑前i件物品在背包容量为w的情况下可以装入的最大价值。第二步状态转移方程对于第i件物品我们只有两种选择装或者不装。不装那么问题就等价于“考虑前i-1件物品容量为w的情况”价值为dp[i-1][w]。装首先需要背包能装下即w weight[i]。如果装那么背包容量会减少weight[i]价值增加value[i]。此时问题等价于“考虑前i-1件物品容量为w - weight[i]的情况”加上当前物品的价值即dp[i-1][w - weight[i]] value[i]。我们要的是最大价值所以在这两种选择中取最大值dp[i][w] max(dp[i-1][w], dp[i-1][w - weight[i]] value[i])其中后一项仅在w weight[i]时有效。第三步与第四步初始化和计算顺序初始化当没有物品或背包容量为0时最大价值为0。即dp[0][...] 0dp[...][0] 0。计算顺序外层循环遍历物品i从1到N内层循环遍历背包容量w从0到W。这样能保证在计算dp[i][w]时dp[i-1][w]和dp[i-1][w - weight[i]]都已经被计算出来。def knapsack_01(N, W, weight, value): # 初始化dp数组多一行一列用于表示0物品/0容量的情况 dp [[0] * (W 1) for _ in range(N 1)] for i in range(1, N 1): # 遍历物品 for w in range(W 1): # 遍历容量 # 默认选择不装第i件物品 dp[i][w] dp[i-1][w] # 如果装得下尝试装看是否更优 if w weight[i-1]: # 注意weight/value数组索引从0开始 dp[i][w] max(dp[i][w], dp[i-1][w - weight[i-1]] value[i-1]) return dp[N][W]第五步空间优化滚动数组观察状态转移方程dp[i][w] max(dp[i-1][w], dp[i-1][w - weight[i]] value[i])当前行i的状态只依赖于上一行i-1的状态。因此我们完全不需要保存整个二维表格只需要一个一维数组dp[w]即可。但这里有一个至关重要的细节内层循环必须从大到小遍历容量W。 为什么因为dp[i][w]依赖于dp[i-1][w]和dp[i-1][w - weight[i]]。如果我们用一维数组并且从小到大遍历w那么在计算dp[w]时dp[w - weight[i]]可能已经被当前第i轮的更新值覆盖了这就相当于第i件物品被重复使用了多次违背了01背包“每个物品只能用一次”的规则。从大到小遍历可以保证在计算dp[w]时dp[w - weight[i]]保存的还是上一轮 (i-1) 的值。def knapsack_01_optimized(N, W, weight, value): dp [0] * (W 1) # 一维dp数组 for i in range(N): # 遍历物品 # 内层循环倒序从W到weight[i] for w in range(W, weight[i] - 1, -1): dp[w] max(dp[w], dp[w - weight[i]] value[i]) return dp[W]实操心得01背包的空间优化是面试必考知识点。务必理解“为何要倒序”。你可以这样记忆01背包是“唯品会”唯一物品内层倒序完全背包是“淘宝”无限物品内层正序。这个类比能帮你快速区分两种背包问题的代码实现。5.2 最长上升子序列LIS一维状态与二分查找优化问题描述给定一个无序的整数数组nums找到其中最长严格递增子序列的长度。子序列不要求连续。第一步定义状态一种最直观的状态定义是dp[i]表示以第i个数字结尾的最长上升子序列的长度。注意这个定义强制要求子序列必须包含nums[i]。第二步状态转移方程如何求dp[i]既然子序列以nums[i]结尾那么我们就需要看看在i之前的所有位置j(0 j i)哪些位置的数比nums[i]小。如果nums[j] nums[i]那么nums[i]就可以接在以 nums[j] 结尾的LIS后面形成一个更长的上升子序列其长度就是dp[j] 1。 我们需要遍历所有满足条件的j找到那个能形成最长序列的即dp[i] max(dp[j] 1)对于所有0 j i且nums[j] nums[i]。 如果找不到这样的j即i前面的数都比它大那么dp[i] 1它自己构成一个序列。第三步与第四步初始化每个位置至少可以以自己结尾所以dp[i] 1。计算顺序从左到右遍历i对于每个i需要遍历它前面所有的j。时间复杂度为O(n^2)。def lengthOfLIS(nums): if not nums: return 0 n len(nums) dp [1] * n # 初始化每个元素自身就是一个长度为1的LIS max_len 1 for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) max_len max(max_len, dp[i]) # 更新全局最大值 return max_len第五步优化贪心二分查找时间复杂度O(n log n)O(n^2)的解法在数据量大时可能超时。有一种更巧妙的、基于“耐心排序”思想的O(n log n)解法。我们维护一个数组tailstails[k]的值代表长度为 k1 的上升子序列的末尾元素的最小值。这个数组一定是严格递增的为什么因为长度更长的子序列其末尾元素不可能比长度短的子序列的末尾元素小。遍历数组nums如果nums[i]比tails中所有元素都大说明它可以接在所有已知子序列后面形成更长的子序列那么就把它追加到tails末尾。否则在tails数组中找到第一个大于等于nums[i]的元素并用nums[i]替换它。这个查找过程可以用二分查找完成。 最终tails数组的长度就是最长上升子序列的长度。这个做法的核心思想是我们总是希望上升子序列末尾的元素尽可能小这样后面才有更多机会接上更大的数使得序列更长。def lengthOfLIS_optimized(nums): tails [] for num in nums: # 二分查找在tails中第一个 num 的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid # 如果left等于tails长度说明num比所有末尾都大 if left len(tails): tails.append(num) else: tails[left] num # 替换使得该长度的子序列末尾元素更小 return len(tails) # tails的长度就是LIS的长度注意事项这个优化算法得到的tails数组其长度是正确的LIS长度但tails本身并不一定是真实的LIS。它只能求出长度。如果需要输出具体的LIS序列通常还是需要用O(n^2)的DP方法并记录路径。6. 避坑指南与高频问题排查动态规划代码写出来但结果不对这是初学者常遇到的问题。下面是一些常见的坑和排查技巧。1. 状态定义不清晰或错误症状状态转移方程怎么都写不对或者写出来非常复杂。排查回到问题本身重新思考你要用哪些信息来描述一个“子问题”。状态变量是否足够是否包含了所有影响决策的关键信息对于背包问题容量通常是必须的对于序列问题以某个位置结尾常常是一个好选择。2. 状态转移方程遗漏情况症状结果比预期小漏算或比预期大多算。排查在推导方程时务必穷举所有可能的选择。比如在背包问题中对于每个物品必须考虑“放”和“不放”两种情况。在LIS问题中对于每个i必须考虑前面所有比它小的j。3. 初始状态设置错误症状程序在边界情况如空数组、容量为0下出错或返回错误结果。排查仔细考虑最小子问题的解是什么。dp[0]或dp[0][0]通常需要手动赋予一个合理的值。对于求最大值/最小值的问题初始值有时需要设为负无穷或正无穷。4. 遍历顺序错误症状这是背包问题空间优化后最容易出错的地方。结果错误物品被重复计算。排查01背包物品唯一使用一维dp数组时内层循环遍历容量必须从大到小。完全背包物品无限使用一维dp数组时内层循环遍历容量必须从小到大。对于多维状态或复杂依赖可以画一个简单的依赖图确保计算当前状态时它所依赖的状态都已经计算好了。5. 数组索引越界症状运行时报IndexError。排查检查dp数组的长度是否足够。通常需要len(dp) n 1或len(dp) W 1来容纳边界状态。在状态转移方程中访问dp[i-1]、dp[i - coin]等下标时一定要先判断i-1 0、i - coin 0。6. 将“子序列”与“子数组”混淆症状用解子数组连续的方法去解子序列不连续问题或者反过来。排查审题时务必看清是“Subsequence”子序列可不连续还是“Subarray”子数组必须连续。它们的状态定义和转移方程通常不同。LIS是子序列问题而“最大子数组和”是子数组问题其状态通常定义为以nums[i]结尾的最大子数组和转移方程为dp[i] max(nums[i], dp[i-1] nums[i])。最后提升动态规划能力没有捷径唯有多练、多总结。从简单的斐波那契、爬楼梯开始到背包、LIS、编辑距离等经典问题每做一题都严格按照“定义状态、写出方程、确定初值、确定顺序、代码实现、思考优化”的流程过一遍。慢慢地你就能培养出对动态规划问题的直觉看到新题也能快速拆解这才是真正掌握了这门“聪明算”的艺术。