★ FEATURED ARTICLE 1. 为什么我要从零写一套动态规划拆解动态规划这四个字几乎是每个学算法的人绕不过去的一道坎。我见过太多人在面试前突击背几道背包问题、最长公共子序列结果换个场景就完全不会了。也见过有人刷了两百道题遇到新题还是第一反应是暴力搜索压根想不到用DP。问题出在哪不是题刷得不够而是没有人把动态规划这件事从根上讲清楚。我自己当年学DP也走了不少弯路。最开始看那些状态转移方程感觉像是变魔术——凭什么这一步就能推到下一步后来慢慢摸索才发现动态规划本质上就是一件事把一个大问题拆成若干个重叠的子问题把子问题的答案记下来避免重复计算。就这么简单。但简单归简单真正要把它用熟需要理解三个核心概念状态定义、状态转移、边界条件。这三个东西缺一个题就做不出来。这套拆解我打算分几篇来写这是第一篇。在这一篇里我会把动态规划最底层的思维方式讲透包括它和递归、贪心、分治的区别为什么需要记忆化状态该怎么定义转移方程该怎么推。后面几篇会分别针对线性DP、区间DP、树形DP、状压DP、数位DP这些常见类型做专项拆解。适合谁看如果你已经会写基本的循环和递归但对动态规划总是似懂非懂或者能看懂题解但自己写不出来那这套内容就是给你准备的。如果你完全没接触过算法建议先补一下数组、循环、递归这些基础再来看会顺畅很多。2. 动态规划到底在解决什么问题2.1 从一道最朴素的题说起先别急着看那些复杂的背包问题。我们从一个最简单的场景开始计算斐波那契数列的第n项。斐波那契数列的定义是f(0)0f(1)1f(n)f(n-1)f(n-2)。用递归写出来是这样的def fib(n): if n 1: return n return fib(n-1) fib(n-2)这段代码逻辑上完全正确但你把它跑一下n50试试大概率你的电脑要转很久。为什么因为存在大量的重复计算。算f(50)需要f(49)和f(48)算f(49)又需要f(48)和f(47)——你看f(48)被算了两次。往下展开重复计算呈指数级增长。时间复杂度是O(2^n)n稍微大一点就炸了。这就是动态规划要解决的核心问题重叠子问题导致的重复计算。解决办法也很直接——算过的就别再算了拿个本子记下来。这个“本子”就是DP数组这个“记下来”的动作就是记忆化。2.2 递归、分治、贪心、DP的区别很多人分不清这几个概念我用自己的理解方式给你捋一下。递归是一种编程技巧函数自己调用自己。它本身不是算法思想只是一种实现手段。分治、DP都可以用递归来实现。分治的核心是“分而治之”——把大问题拆成互不重叠的子问题分别解决后合并结果。归并排序就是典型的分治左半边排序、右半边排序两个有序数组合并。注意关键词“互不重叠”分治的子问题之间是没有交集的。动态规划的子问题是重叠的。f(48)在算f(50)和算f(49)的时候都要用到这就是重叠。正因为重叠才有必要把结果存起来复用。如果子问题不重叠那用分治就行了存了也没人用。贪心是另一种思路每一步都选当前看起来最优的不回头。贪心的难点在于证明“局部最优能导致全局最优”这个证明往往比DP还难。而且很多问题贪心根本做不了比如背包问题你按性价比贪心选最后可能装不满。用一个表格对比一下算法思想子问题关系是否回退典型场景分治互不重叠不回退归并排序、快速排序贪心无子问题不回退活动选择、霍夫曼编码动态规划重叠不回退背包、最长子序列回溯重叠回退八皇后、全排列这张表你多看几遍面试的时候被问到区别直接就能答上来。2.3 什么时候该想到DP这是最关键的问题。题目摆在面前你怎么知道该用DP我总结了一个简单的判断流程你照着走就行问题要求最优解——最大值、最小值、最长、最短、最多、最少。如果只是问“有没有”那可能是搜索或BFS。问题可以拆成子问题——当前状态可以由之前的状态推导出来。比如“走到第i级台阶的方法数”可以由“走到第i-1级”和“走到第i-2级”推导。子问题有重叠——不同的路径会到达相同的状态。如果每个子问题只被用一次那分治就够了。满足最优子结构——全局最优解包含子问题的最优解。这句话听起来绕举个例子就明白了从A到C的最短路径经过B那么A到B的路径也一定是最短的。如果不满足这个性质DP就不适用。四个条件同时满足基本就可以确定用DP了。前两个条件帮你识别问题类型后两个条件帮你确认DP可行。注意不要一上来就套模板。先想清楚状态是什么、转移是什么再去写代码。我见过太多人上来就写for循环写到一半发现状态定义错了全部推倒重来。3. 动态规划的核心要素拆解3.1 状态定义DP的地基状态定义是动态规划里最难也最重要的一步。状态定义对了转移方程往往水到渠成状态定义错了怎么推都推不出来。什么叫状态简单说状态就是子问题的答案。但关键在于你要用什么样的维度来描述这个子问题。拿爬楼梯问题举例一次可以爬1级或2级问爬到第n级有多少种方法。这里的子问题是什么是“爬到第i级有多少种方法”。所以状态就是dp[i]表示爬到第i级的方法数。一维就够了。再看背包问题有n个物品每个有重量和价值背包容量为W求最大价值。这里的子问题是什么是“前i个物品在容量为j的情况下能装的最大价值”。所以状态是dp[i][j]两个维度物品数量和容量。状态定义的维度怎么确定我的经验是看问题中有几个变量在变化。爬楼梯只有“位置”一个变量所以一维。背包有“选到第几个物品”和“当前容量”两个变量所以二维。如果还有“是否使用过某个特殊物品”这种状态那就再加一维。这里有个常见的坑状态定义要能覆盖所有情况不能有遗漏。比如背包问题如果你只定义dp[j]表示容量为j时的最大价值那在遍历物品的时候就需要倒序遍历来保证每个物品只被选一次。这个细节后面会详细讲。3.2 状态转移方程从子问题到原问题状态转移方程描述的是当前状态如何由之前的状态推导出来。还是爬楼梯。dp[i]表示爬到第i级的方法数。那dp[i]怎么来你最后一步要么是从第i-1级爬1级上来的要么是从第i-2级爬2级上来的。所以dp[i] dp[i-1] dp[i-2]。这就是转移方程。再看背包。dp[i][j]表示前i个物品在容量j下的最大价值。对于第i个物品你有两个选择选它或者不选它。不选dp[i][j] dp[i-1][j]选前提是j weight[i]dp[i][j] dp[i-1][j-weight[i]] value[i]取两者的最大值就是转移方程。推转移方程的通用思路是考虑最后一步做了什么选择。爬楼梯的最后一步是爬1级还是2级背包的最后一步是选第i个物品还是不选。把最后一步的所有可能性列出来每种可能性对应一个子问题取最优的那个就是转移方程。3.3 边界条件别让数组越界边界条件是DP里最容易被忽略、也最容易出错的地方。爬楼梯的边界是什么dp[0] 1站在地面算一种方法dp[1] 1爬1级只有一种方法。如果你忘了定义dp[0]那dp[2] dp[1] dp[0]就没法算了。背包的边界是什么dp[0][j] 0前0个物品不管容量多大价值都是0dp[i][0] 0容量为0装不了任何东西价值为0。边界条件的原则是最小子问题的答案是什么。这个答案必须是已知的、不需要再推导的。通常对应的是“没有物品”“容量为0”“位置为0”这些极端情况。实操心得写完转移方程后先手动算几个小值验证边界。比如爬楼梯手动算dp[0]到dp[5]看看结果对不对。如果边界错了后面全错。3.4 遍历顺序谁先谁后很关键有了状态、转移方程、边界条件接下来就是确定遍历顺序。遍历顺序的原则是计算dp[i]的时候它依赖的那些状态必须已经算好了。爬楼梯dp[i]依赖dp[i-1]和dp[i-2]所以从前往后遍历i从小到大。背包dp[i][j]依赖dp[i-1][j]和dp[i-1][j-weight[i]]都是上一行的状态所以外层遍历物品i内层遍历容量j从前往后或从后往前都可以二维情况下。但如果把背包优化成一维数组遍历顺序就变得非常关键。一维情况下dp[j]依赖dp[j]上一轮的和dp[j-weight[i]]上一轮的。如果j从小到大遍历dp[j-weight[i]]可能已经被当前物品更新过了导致一个物品被选多次。所以必须从大到小遍历j。这个细节是背包问题最容易出错的地方后面会专门讲。4. 从暴力递归到动态规划的完整过程4.1 第一步写出暴力递归动态规划不是凭空想出来的它通常是从暴力递归优化而来的。所以第一步别想什么DP先把暴力解法写出来。以爬楼梯为例暴力递归是这样的def climb(n): if n 1: return 1 return climb(n-1) climb(n-2)这段代码的问题前面说过了重复计算太多。但它的好处是逻辑清晰直接对应问题的定义。再以最长递增子序列LIS为例。暴力递归的思路是对于每个位置i要么选它要么不选它。如果选了下一个选的必须比它大。def lis(nums, prev, cur): if cur len(nums): return 0 # 不选当前元素 taken lis(nums, prev, cur 1) # 选当前元素前提是比前一个大 not_taken 0 if prev 0 or nums[cur] nums[prev]: not_taken 1 lis(nums, cur, cur 1) return max(taken, not_taken)这个递归的时间复杂度是指数级的但它是我们推导DP的基础。4.2 第二步加记忆化暴力递归写出来之后下一步就是找重复计算。怎么找看递归函数的参数。如果不同的调用路径传入了相同的参数那就是重复计算。爬楼梯的递归只有一个参数n不同的路径会到达相同的n所以可以用一个一维数组memo来记录。def climb(n, memo): if n 1: return 1 if memo[n] ! -1: return memo[n] memo[n] climb(n-1, memo) climb(n-2, memo) return memo[n]LIS的递归有两个参数prev和cur所以需要二维数组memo[prev][cur]。但prev的范围是-1到n-1cur的范围是0到n所以memo的大小是(n1) x (n1)。加记忆化之后时间复杂度从指数级降到了O(n)或O(n^2)。这就是记忆化搜索也叫自顶向下的DP。4.3 第三步改成自底向上记忆化搜索已经能AC大部分题目了但有些场景下自底向上的写法更优没有递归栈的开销可以优化空间而且更容易发现可以复用的状态。改自底向上的方法把递归函数的参数变成DP数组的维度把递归的终止条件变成DP数组的初始化把递归的调用关系变成遍历顺序。爬楼梯的自底向上def climb(n): if n 1: return 1 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]LIS的自底向上def lis(nums): n len(nums) if n 0: return 0 dp [1] * n for i in range(1, n): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) return max(dp)注意LIS的DP定义和递归定义不太一样。递归里是“从prev到cur能选出的最长递增子序列”DP里是“以nums[i]结尾的最长递增子序列”。这两种定义都是对的但DP的定义更容易写成自底向上的形式。这也是我想强调的一点状态定义不是唯一的选择最容易推导转移方程的那个。4.4 三种写法的对比写法优点缺点适用场景暴力递归逻辑直观容易想到指数级时间大输入超时理解问题结构记忆化搜索保留递归逻辑剪掉重复递归栈开销可能爆栈状态转移复杂、遍历顺序不明确自底向上无栈开销可优化空间遍历顺序需要思考状态转移清晰、需要空间优化我的建议是先用暴力递归理解问题再加记忆化确保正确最后改自底向上优化。不要一上来就追求最优写法先把问题做对再做好。5. 新手最容易踩的五个坑5.1 状态定义不完整这是最致命的错误。状态定义不完整意味着有些信息丢失了导致转移方程推不出来或者推出来是错的。举个例子股票买卖问题限制最多交易k次。如果你只定义dp[i]表示第i天能获得的最大利润那就丢失了“已经交易了几次”这个信息。正确的定义应该是dp[i][j][0/1]表示第i天、已经交易了j次、当前是否持有股票时的最大利润。怎么判断状态定义是否完整我的方法是看转移方程里用到的所有信息是否都能从状态中获取。如果转移的时候需要知道某个信息但状态里没有那就说明定义不完整。5.2 边界条件写错边界条件写错通常有两种情况一种是忘了初始化另一种是初始化成了错误的值。比如求最小值的DP初始化的时候应该把dp数组设成一个大数比如无穷大而不是0。如果你设成0那取min的时候永远取不到正确的值。反过来求最大值的DP应该初始化成负无穷或0取决于问题是否允许负数。还有一个常见的坑是数组越界。比如dp[i-2]在i1的时候会越界所以循环要从i2开始或者加个判断。5.3 遍历顺序搞反遍历顺序搞反在背包问题的一维优化里特别常见。二维背包的转移是dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)。注意这里依赖的是dp[i-1]也就是上一行的状态。如果压缩成一维dp[j] max(dp[j], dp[j-w] v)这里的dp[j]和dp[j-w]都必须是上一轮的值。如果j从小到大遍历dp[j-w]可能已经被当前物品更新过了那就变成了完全背包每个物品可以选多次。所以必须从大到小遍历j。这个点我当年也是踩了好几次坑才记住的。记不住怎么办画个表手动模拟一遍看看从小到大和从大到小的区别印象就深了。5.4 空间优化过度空间优化是好事但不要为了优化而优化。有些题目的状态转移依赖多个之前的状态强行压缩空间反而容易出错。比如有些区间DPdp[i][j]依赖dp[i1][j]和dp[i][j-1]这种依赖关系压缩成一维之后遍历顺序会变得非常复杂容易写错。除非空间实在不够比如n5000二维数组开不下否则没必要压缩。我的原则是先写二维的能过就行。过不了再考虑优化。面试的时候也是先写清晰的版本面试官如果问能不能优化空间再讨论。5.5 把DP当模板背这是最根本的问题。DP的题型太多了你不可能背完所有模板。背模板的结果就是遇到新题就懵。正确的学习方式是理解DP的核心思想掌握推导状态和转移的方法然后通过做题积累经验。每做一道题问自己三个问题状态为什么这么定义转移方程怎么推出来的边界条件为什么是这样想清楚这三个问题比刷十道题都有用。实操心得我习惯在做完一道DP题之后把状态定义和转移方程用注释写在代码旁边。过一周再回来看如果能看懂自己写的注释说明真的理解了如果看不懂说明当时是蒙的需要重新做。6. 一道完整例题的拆解全过程6.1 题目描述与初步分析我们用一道经典的题来走一遍完整流程零钱兑换。题目给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。每种硬币的数量是无限的。比如coins [1, 2, 5]amount 11答案是3551。初步分析要求“最少硬币个数”这是最优解问题。可以拆成子问题凑成金额i需要的最少硬币数可以由凑成金额i-coin的答案推导出来。子问题有重叠凑11可以用56或29等不同路径到达。满足最优子结构。所以可以用DP。6.2 状态定义与转移方程推导状态定义dp[i]表示凑成金额i所需的最少硬币个数。转移方程对于金额i我们可以选择任意一种硬币coin。如果选了coin那剩下的金额是i-coin需要的硬币数是dp[i-coin]1。我们要找的是所有选择中最小的那个。所以dp[i] min(dp[i-coin] 1)对所有coin i。边界条件dp[0] 0凑成金额0需要0个硬币。其他dp[i]初始化为一个不可能的大值比如amount1表示暂时无法凑成。遍历顺序dp[i]依赖dp[i-coin]i-coin i所以从前往后遍历i。6.3 代码实现与逐步调试def coinChange(coins, amount): # 初始化dp数组用amount1表示无穷大 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手动模拟一下coins[1,2,5]amount5的过程dp[0] 0dp[1] min(dp[1-1]1) dp[0]1 1dp[2] min(dp[2-1]1, dp[2-2]1) min(2, 1) 1dp[3] min(dp[3-1]1, dp[3-2]1) min(2, 2) 2dp[4] min(dp[4-1]1, dp[4-2]1) min(3, 2) 2dp[5] min(dp[5-1]1, dp[5-2]1, dp[5-5]1) min(3, 3, 1) 1结果正确。6.4 复杂度分析与优化空间时间复杂度外层循环amount次内层循环coins的长度次所以是O(amount * n)n是硬币种类数。空间复杂度O(amount)一个一维数组。能不能优化这个问题的空间已经是一维了没法再压缩。时间上如果硬币种类很多可以考虑先去重或者排序但整体复杂度不变。还有一个变体是求“有多少种凑法”那个转移方程是dp[i] dp[i-coin]注意遍历顺序会影响结果组合数还是排列数这个后面单独讲。6.5 从这道题能学到什么零钱兑换这道题涵盖了DP的核心要素状态定义一维、转移方程取min、边界条件dp[0]0、遍历顺序从前往后。而且它还有一个特殊之处每种硬币数量无限这对应的是完全背包问题。如果是每种硬币只能用一次那就是0-1背包遍历顺序要反过来。通过这一道题你可以把DP的基本流程走一遍。后面遇到类似的题比如“完全平方数”“整数拆分”都是同样的套路。7. 我个人的练习路径建议7.1 按类型循序渐进DP的题型很多不要一上来就刷难题。我建议的练习顺序是线性DP爬楼梯、打家劫舍、最长递增子序列。这些题状态是一维或二维的转移方程直观适合入门。背包DP0-1背包、完全背包、多重背包。背包问题是DP的经典模型很多题都可以转化为背包。区间DP最长回文子序列、石子合并。状态是区间转移方程通常涉及分割点。树形DP二叉树的最大路径和、打家劫舍III。在树上做DP通常用递归实现。状压DP旅行商问题、集合覆盖。用二进制表示状态适合n比较小的情况。数位DP统计满足某些条件的数字个数。套路比较固定但细节多。每个类型刷5-10道题基本就能掌握套路。不要贪多关键是每道题都吃透。7.2 每道题必做的三件事我做DP题有一个固定的流程分享给你第一件事手推小案例。拿到题之后先别写代码拿纸笔手动算几个小值。比如n1,2,3,4的时候答案是多少。这个过程帮你理解问题的结构也帮你验证后面的代码。第二件事写暴力递归。手推完之后写出暴力递归的解法。不要嫌它慢它的价值在于逻辑清晰是你推导DP的基础。第三件事优化并对比。加记忆化改自底向上然后对比三种写法的运行时间和代码复杂度。这个过程让你理解DP的优化思路。做完这三件事这道题才算真正消化了。如果只是看题解然后抄一遍代码下次遇到类似的题还是不会。7.3 什么时候算真正掌握了很多人问我怎么知道自己DP算入门了我的判断标准是拿到一道新题你能在10分钟内确定状态定义和转移方程。注意是确定不是猜。你能说清楚为什么这么定义状态为什么转移方程是这样边界条件为什么是这些。如果做不到说明还需要练。另一个标准是你能把一道DP题讲给别人听并且对方能听懂。教是最好的学。如果你能把一道题的状态定义、转移方程、边界条件、遍历顺序讲清楚那说明你真的理解了。动态规划这个东西入门确实需要一点时间但一旦开窍了后面就是一马平川。我当年也是卡了很久突然有一天就想通了。想通的那一刻回头看之前那些题感觉完全不一样了。这套拆解的第一篇就到这里。下一篇我会专门讲线性DP把最长递增子序列、最大子数组和、打家劫舍这些经典题一个个拆开揉碎。如果你在学DP的过程中遇到什么问题或者有什么想让我拆解的题型可以留言告诉我。
阅读完成 · 觉得有帮助？
