文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载本篇技术指南以 算法/198.精读《算法 - 动态规划》.md 为主体骨架系统讲解动态规划与暴力、回溯算法的本质区别从最优子结构、重复子问题、无后效性三大特征出发以爬楼梯、最大子序和、最长递增子序列、最长有效括号、栅栏涂色、编辑距离六道经典题目为实战案例覆盖一维、嵌套、多维与非字符串场景并深入缓存优化滚动缓存与状态定义技巧。读完本文你将掌握写出任意动态规划状态转移方程的方法论并能在真实面试与工程问题中快速判断这道题能不能用 DP 解。为什么必须掌握动态规划很多人觉得动态规划很难甚至认为面试出动态规划题目是在为难候选人这可能产生一个错误潜意识认为动态规划不需要掌握。其实动态规划非常有必要掌握非常锻炼思维。动态规划是非常锻炼脑力的题目虽然有套路但每道题解法思路差异很大作为思维练习非常合适。非常实用。动态规划听起来很高级但实际上思路和解决的问题都很常见。动态规划用来解决一定条件下的最优解问题比如自动寻路哪种走法最优背包问题装哪些物品空间利用率最大零钱兑换怎么用最少的硬币凑零钱这些问题乍一看都挺难毕竟都不是一眼能看出答案的问题。但得到最优解又非常重要——谁能忍受游戏中寻路算法绕路呢谁不希望背包放的东西更多呢所以动态规划是必须掌握的算法能力。动态规划的本质更聪明的暴力动态规划不是魔法它也是通过暴力方法尝试答案只是方式更加聪明使得实际上时间复杂度并不高。动态规划与暴力、回溯算法的区别上面这句话说明了所有动态规划问题都能通过暴力方法解决。是的所有最优解问题都可以通过暴力方法尝试以及回溯算法最终找出最优的那个。暴力算法几乎可以解决一切问题。回溯算法通过暴力尝试不同分支最终选择结果最优的线路。动态规划也有分支概念但不用把每条分支尝试到终点而是在走到分叉路口时可以直接根据前面各分支的表现直接推导出下一步的最优解。仓库姊妹篇 算法/200.精读《算法 - 回溯》.md 对二者的关系有更深入的对比动态规划之所以可以省去大量无效分支是因为可以利用缓存存储之前的结果避免重复子问题的重复计算而回溯面临的问题通常具有后效性、不存在重复子问题所以无法利用缓存加速代价时间复杂度也更高——只有当没有更优算法时才应当考虑回溯算法。然而无论是直接推导还是前面各分支判断都是有条件的。动态规划可解问题需同时满足以下三个特点存在最优子结构。存在重复子问题。无后效性。特征一存在最优子结构即子问题的最优解可以推导出全局最优解。什么是子问题比如寻路算法中走完前几步就是相对于走完全程的子问题必须保证走完全程的最短路径可以通过走完前几步推导出来才可以用动态规划。不要小看这第一条动态规划就难在这里你到底如何将最优子结构与全局最优解建立上关系对于爬楼梯问题由于每层台阶都是由前面台阶爬上来的因此必然存在一个线性关系推导。如果变成二维平面寻路呢那么就升级为二维问题存在两个变量i,j与上一步之间关系了。如果是背包问题同时存在物品数量i、物品重量j和物品质量k三个变量呢那就升级为三维问题需要寻找三个之间的关系。依此类推复杂度可以上升到 N 维维度越高思考的复杂度就越高空间复杂度就越需要优化。特征二存在重复子问题即同一个子问题在不同场景下存在重复计算。比如寻路算法中同样两条路线的计算中有一段路线是公共的、是计算的必经之路那么只算一次就好了——当计算下一条路时遇到这个子路直接拿第一次计算的缓存即可。典型例子是斐波那契数列对于f(3)与f(4)都要计算f(1)与f(2)因为f(3) f(2) f(1)而f(4) f(3) f(2) f(2) f(1) f(2)。这是动态规划与暴力解法的关键区别动态规划之所以性能高是因为不会对重复子问题进行重复计算算法上一般通过缓存计算结果或者自底向上迭代的方式解决但核心是这个场景要存在重复子问题。实践提示当你觉得暴力解法可能很傻、存在大量重复计算时就要想想是哪里存在重复子问题是否可以用动态规划解决了。特征三无后效性即前面的选择不会影响后面的游戏规则。寻路算法中不会因为前面走了 B 路线而对后面路线产生影响。斐波那契数列因为第 N 项与前面的项是确定关联没有选择一说所以也不存在后效性问题。什么场景存在后效性呢比如你的人生是否能通过动态规划求最优解其实是不行的因为你今天的选择可能影响未来人生轨迹——比如你选择了计算机这个职业会直接影响到工作的领域、接触到的人后面的人生路线因此就完全变了所以根本无法与选择了土木工程的你进行比较因为人生赛道都变了。有同学可能觉得这样局限是不是很大其实不然无后效性的问题仍然很多比如背包放哪件物品、当前走哪条路线、用了哪些零钱都不会影响整个背包大小、整张地图的地形、以及你最重要付款的金额。更专业的补充动态规划之所以无法处理有后效性问题原因是其dp(i) F(dp(j))其中0 j i的推导结构——i通过i-1推导如果i-1的某种选择会对i的选择产生影响那么这个推导就是无效的。仓库 算法/200.精读《算法 - 回溯》.md 明确指出这正是回溯算法与动态规划的分水岭回溯的每条分支判断相互独立即便前面的选择具有后效性这个后效性也可以在这条选择线路持续影响下去而不影响其他分支。另外仓库 算法/286.精读《算法题 - 地下城游戏》.md 给出了一个看似能用 DP、实则踩中后效性陷阱的真实案例正向计算最低初始健康点数时dp[i][j]居然还由后面的值攻击力为 3 的恶魔决定这就是典型的有后效性导致 DP 失败最终需要从右下角逆向推导才能消除后效性。这个案例很好地印证了无后效性这条特征的实战意义。解法套路状态转移方程解决动态规划问题的核心就是写出状态转移方程。所谓状态转移即通过某些之前步骤推导出未来步骤。状态转移方程一般写为dp(i) 一系列 dp(j) 的计算其中j i。其中i与dp(i)的含义很重要一般dp(i)直接代表题目的答案i就有技巧了。比如斐波那契数列dp(i)表示的答案就是最终结果i表示下标——由于斐波那契数列直接把状态转移方程告诉你了f(x) f(x-1) f(x-2)那么根本连推导都不必了。对于复杂问题难在如何定义i的含义以及下一步状态如何通过之前状态推导。这个做多了题目就有体会。下面直接看例子。实战一爬楼梯最简单的线性 DP爬楼梯是一道简单题题目如下假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢给定n是一个正整数首先dp(i)就是问题的答案解法套路dp(i)大部分情况就是答案这样解题思路会最简化即爬到第i阶台阶的方法数量那么i自然就是要爬到第几阶台阶。验证三大特征最优子结构因为只能往上爬所以第i阶台阶有几种爬法完全取决于前面有几种爬法而一次只能爬 1 或 2 个台阶所以第i阶台阶只可能从第i-1或i-2个台阶爬上来的所以第i个台阶的爬法就是i-1与i-2总爬法之和。重复子问题爬楼梯和斐波那契数列类似最终的状态转移方程是一样的所以显然存在重复子问题。直观来看也容易分析10 阶台阶的爬法包含了 8、9 阶的爬法而 9 阶台阶爬法包含了 8 阶的所以存在重复子问题。无后效性前面选择一次爬 1 个或 2 个台阶并不会影响总台阶数也不会影响你下一次能爬的台阶数所以无后效性。反例如果你爬了 2 个台阶后因为太累下次只能爬 1 个台阶就属于有后效性或者只要你一共爬了 3 次 2 阶就会因为太累而放弃爬楼梯、直接下楼休息那么问题提前结束也属于有后效性。所以爬楼梯的状态转移方程为dp(i) dp(i-1) dp(i-2)dp(1) 1dp(2) 2注意因为 1、2 阶台阶无法应用通用状态转移方程所以要特殊枚举。这种枚举思路在代码里其实就是递归终结条件——作为函数dp(i)不能无限递归当i取值为 1 或 2 时直接返回枚举结果。所以在写递归时一定要优先写上递归终结条件。对于第一阶台阶只有一种爬法对于第二阶台阶可以直接两步跨上来也可以走两个一步所以有两种爬法。至此此题得解。爬楼梯的三种代码形态形态一朴素递归存在大量重复计算不推荐function dp(i: number) { switch (i) { case 1: return 1; case 2: return 2; default: return dp(i - 1) dp(i - 2); } } return dp(n);这样写重复计算了子结构所以我们不要每次傻傻的执行dp(i - 1)因为这样计算了超多重复子问题需要用缓存兜底。形态二一维线性缓存自底向上填充const cache: number[] []; function dp(i: number) { switch (i) { case 1: cache[i] 1; break; case 2: cache[i] 2; break; default: cache[i] cache[i - 1] cache[i - 2]; } return cache[i]; } // 既然用了缓存最好自底向上递归这样前面的缓存才能优先算出来 for (let i 1; i n; i) { dp(i); } return cache[n];这种形态的时间复杂度为O(n)空间复杂度为O(n)也是自底向上迭代 缓存这一经典优化思想的代码化表达——与文首动态规划通过缓存计算结果或自底向上迭代避免重复计算的论述完全对应。形态三滚动缓存空间压缩到 O(1)更高级的缓存模式还有滚动缓存。我们观察发现这道题缓存空间开销是O(n)但每次缓存只用了上两次的值所以计算到dp(4)时cache[1]就可以扔掉了或者说我们可以滚动利用缓存让cache[3]占用cache[1]的空间那么整体空间复杂度可以降低到O(1)const cache: [number, number] []; function dp(i: number) { switch (i) { case 1: cache[i % 2] 1; break; case 2: cache[i % 2] 2; break; default: cache[i % 2] cache[(i - 1) % 2] cache[(i - 2) % 2]; } return cache[i % 2]; } for (let i 1; i n; i) { dp(i); } return cache[n % 2];通过取余巧妙让缓存永远交替占用cache[0]与cache[1]达到空间利用最大化。使用前提这道题因为状态转移方程是连续用了前两个值所以可以这么优化如果遇到用到之前所有缓存的状态转移方程如后面的最长递增子序列就无法使用滚动缓存方案了。此外还有更高级的多维缓存后面提到的时候再说。实战二最大子序和连 or 断决策最大子序和是一道简单题题目如下给定一个整数数组nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。首先按照爬楼梯的套路dp(i)就表示最大和由于整数数组可能存在负数所以越多数相加和不一定越大。接着看i对于数组问题大部分i都可以代表以第i位结尾的字符串那么dp(i)就表示以第i位结尾的字符串的最大和。可能你觉得以i结尾就只能是[0-i]范围的值那么[j-i]范围的字符串不就被忽略了其实不然[j-i]如果是最大和也会被包含在dp(i)里因为我们状态转移方程可以选择不连上dp(i-1)。现在开始解题题目是最大和的连续子数组一般连续的都比较简单因为对于dp(i)要么和前面连上要么和前面断掉所以状态转移方程为dp(i) dp(i-1) nums[i]如果dp(i-1) 0。dp(i) nums[i]如果dp(i-1) 0。怎么理解呢第i个状态可以直接由第i-1个状态推导出来既然dp(i)是以第i个字符串结尾的最大和那么dp(i-1)就是以第i-1个字符串结尾的最大和而且此时dp(i-1)已经算出来了。因为字符串是连续的所以dp(i)要么是dp(i-1) nums[i]要么就直接是nums[i]。选择哪种取决于前面的dp(i-1)是否是正数——因为以i结尾一定包含nums[i]所以nums[i]不管是正还是负都一定要带上。所以容易得知dp(i-1)如果是正数就连起来否则就不连。这道题如果再复杂一点不连续怎么办呢让我们看看最长递增子序列问题。实战三最长递增子序列需要遍历全部前驱 j最长递增子序列是一道中等题题目如下给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。仓库 前沿技术/192.精读《DOM diff 最长上升子序列》.md 有详细解析过这道题包括还有更优的贪心解法不过本文聚焦在动态规划方法上。这道题与上一道的区别就是首先递增其次不连续。按照套路dp(i)表示以第i个字符串结尾的最长上升子序列长度那么重点是dp(i)怎么通过之前的推导出来由于是不连续的因此不能只看dp(i-1)了——因为nums[i]项与dp(j)其中0 j i组合后都可能达到最大长度因此需要遍历所有j尝试其中最大长度的组合。所以状态转移方程为dp[i] max(dp[j]) 1其中0 j i且num[j] num[i]。这道题的出现预示着较为复杂的状态转移方程的出现第i项不是简单由i-1推导而是由之前所有dp(j)推导其中0 j i。从源码层面看也正因为要遍历所有前驱j求最大值dp(i)依赖了之前的全部缓存值滚动缓存方案在此失效——这与爬楼梯仅依赖前两个值的缓存结构形成鲜明对比也呼应了前面提到的滚动缓存使用前提。除此之外还有推导变种根据dp(dp(i))推导即函数里套函数。这类问题由于加深了一层思考脑回路所以相对更难。我们看一道这样的题目最长有效括号。实战四最长有效括号嵌套 DP最长有效括号是道困难题题目如下给你一个只包含(和)的字符串找出最长有效格式正确且连续括号子串的长度。这道题之所以是困难题就因为状态转移方程存在嵌套思维。首先按套路定义dp(i)为答案即以第i下标结尾的字符串中最长有效括号长度。看出来了吗一般字符串题目中i都是以字符串下标结尾来定义很少有定义为开头或者别的定义行为。当然非字符串问题就不是这样了这个在后面再说。继续题目如果s[i]是(那么不可能组成有效括号因为最右边一定不闭合所以考虑s[i]为)的场景。场景一s[i-1]为(构成...()之势最后两个自成合法闭合所以只要看前面的即可即dp(i-2)dp(i) dp(i-2) 2场景二s[i-1]是)构成...))的状态那么只有i-1是合法闭合的且这个合法闭合段之前必须是(与第i项形成闭合才构成此时最长有效括号长度dp(i) dp(i-1) dp(i - dp(i-1) - 2) 2可以这样理解这个式子dp(i-1)就是已闭合段想象为一条横线的长度如果红色括号即s[i - dp(i-1) - 1]与第i项匹配长度又 2最后别忘了最左边如果有满足匹配的也要带上这就是dp(i - dp(i-1) - 2)所以加到一起就是这种场景的括号最大长度。到这里一维动态规划问题的深度基本上探索完了。在进入多维动态规划问题前还有一类一维动态规划问题属于表达式不难、也没有这么复杂的嵌套 DP但是思维复杂度极高——你一定不要盯着全流程看那样复杂度太高你需要充分认可dp(i-x)已经算出来部分的含义进行高度抽象的思考。实战五栅栏涂色对方案总数做抽象思考栅栏涂色是一道困难题题目如下有k种颜色的涂料和一个包含n个栅栏柱的栅栏每个栅栏柱可以用其中一种颜色进行上色。你需要给所有栅栏柱上色并且保证其中相邻的栅栏柱最多连续两个颜色相同。然后返回所有有效涂色的方案数。这道题k和n都非常巨大常规暴力解法甚至普通 DP 都会超时。选择i的含义也很重要这里i到底代表用几种颜色还是几个栅栏呢选择栅栏会好做一些因为栅栏是上色的主体。这样dp(i)就表示上色前i个栅栏的所有涂色方案。递归终止条件由于最多连续两个颜色相同因此dp(0)与dp(1)分别是k与k*k——每个栅栏随便刷颜色自由组合。那么dp(2)有三个栅栏非法情况是三个栅栏全同色所以用所有可能减掉非法即可非法场景只有k种所以结果是k*k*k - k。一般情况推导对于dp(i)有几种涂色方案呢直接思考情况太多我们把情况一分为二考虑i与i-1颜色相同与不同两种情况i与i-1颜色相同为了合法i-1肯定不能与i-2颜色相同否则就三个同色。这样的话不管i-2是什么颜色i-1与i都只能少取一种颜色少取的颜色就是i-2的颜色因此[i-1, i]这个区间有k-1种取色方案前面有dp(i-2)种取色方案相乘就是最终方案数dp(i-2) * (k-1)。关键理解这背后其实存在动态思维即每种场景的k-1都是不同的颜色组合只是无论前面dp(i-2)是何种组合后面两个栅栏一定有k-1种取法——虽然颜色组合的色值不同但颜色组合数量是不变的所以可以统一计算。理解这一点非常关键。i与i-1颜色不同第i项只有k-1种取法一样也是动态的因为永远不能和i-1颜色相同。最后乘上dp(i-1)的取色方案就是总方案数dp(i-1) * (k-1)。所以最后总方案数就是两者之和dp(i) dp(i-2) * (k-1) dp(i-1) * (k-1)本题的深刻启示这道题的不同之处在于变化太多——任何一个栅栏取的颜色都会影响后面栅栏要取的颜色乍一看觉得是个有后效性的题目无法用动态规划解决。但实际上虽然有后效性但如果进行合理的拆解后面栅栏的总可能性k-1是不变的所以考虑总可能性数量是无后效性的——因此站在方案总数上进行抽象思考才可能破解此题。进入多维二维动态规划与编辑距离二维动态规划就是用两个变量表示 DP即dp(i,j)一般在二维数组场景出现较多当然也有一些两个数组之间的关系也属于二维动态规划。为了继续探讨字符串问题这里选择字符串问题的二维动态规划范例编辑距离。编辑距离是一道困难题题目如下给你两个单词word1和word2请你计算出将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作插入一个字符删除一个字符替换一个字符只要是字符串问题基本上i都表示以第i项结尾的字符串但这道题有两个单词字符串为了考虑任意匹配场景必须用两个变量表示即i、j分别表示word1与word2结尾下标时最少操作次数。那么对于dp(i,j)考虑word1[i]与word2[j]是否相同最后通过双重递归——先递归i在递归内再递归j——答案就出来了。最后一个字符相同word1[i] word2[j]由于最后一个字符不用改就相同了所以操作次数就等价于考虑到前一个字符dp(i,j) dp(i-1,j-1)。最后一个字符不同那么最后一步有三种模式可以得到替换dp(i,j) dp(i-1,j-1) 1。替换最后一个字符只要一步并且和前面字符没什么关系所以前面的最小操作次数直接加过来。插入word1插入一个字符变成word2。变换到这一步时word1比word2少一个单词其它都一样要变换到这一步就要进行dp(i,j-1)的变换因此dp(i,j) dp(i,j-1) 1。删除word1删除一个字符变成word2。同理要进行dp(i-1,j)的变化后多一步删除因此dp(i,j) dp(i-1,j) 1。由于题目取操作最少次数所以这三种情况取最小即可dp(i,j) min(dp(i-1,j-1), dp(i,j-1), dp(i-1,j)) 1。所以同时考虑了最后一个字符是否相同后合并的状态转移方程就是最终答案。终止条件即i或j为 -1 时的情况。因为状态转移方程i和j不断减小肯定会减少到 0 或 -1。相比 0字符串还有一个字符考虑 -1字符串为空更方便因此我们以 -1 作为边界条件当i为 -1 时word1为空此时要变换为word2只有插入j次是最小操作次数因此dp(i,j) j。同理当j为 -1 时word2为空此时要删除i次因此dp(i,j) i。源码佐证编辑距离的完整实现与边界处理仓库 算法/288.精读《算法题 - 编辑距离》.md 给出了这道题可运行的完整 TypeScript 实现对边界条件的处理尤其值得借鉴function minDistance(word1: string, word2: string): number { // 任意一个字符串为空时执行非空字符串长度次数的增或删 if(word1 || word2 ) { return word1.length word2.length } const dp new Map() function getDp(i: number, j: number) { return dp.get(${i},${j}) } function calcDp(i: number, j: number) { // 兼容下边界情况 if (i 0 j 0) { return word1[0] word2[0] ? 0 : 1 } if (word1[i] word2[j]) { return getDp(i-1, j-1) } return Math.min( // i-1, j: 删除第 i 项 getDp(i-1, j) 1, // i, j-1: 增加第 i 项 getDp(i, j-1) 1, // i-1, j-1: 替换第 i 项 getDp(i-1, j-1) 1 ) } for (let i 0; i word1.length; i) { dp.set(${i},-1, i 1) } for (let j 0; j word2.length; j) { dp.set(-1,${j}, j 1) } for (let i 0; i word1.length; i) { for (let j 0; j word2.length; j) { dp.set(${i},${j}, calcDp(i, j)) } } return getDp(word1.length-1, word2.length-1) };实现中的关键点是当i0时dp(i-1,j)就出现了i-1的情况因此对于i、j都要提前计算一下为-1时的值当下标为-1时等价于该字符串为空那么空字符串如何转换为word2或word1如何转换为空字符串呢只要执行对方下标 1 次的增或删就行了。从工程角度用Map以字符串键i,j存取状态是记忆化搜索Memoization的自然实现——这也再次印证了动态规划的两大实现范式自底向上的迭代填表与带缓存的递归。非字符串场景的动规问题说到这相信你在字符串动规问题上已经如鱼得水了再看看非字符串场景的动规问题。非字符串场景的动规比较经典的有三个矩形路径最小距离 / 最大收益。背包问题以及变种。打家劫舍问题。这些问题解决方式都一样只是对于dp(i)的定义略有区别矩形问题dp(i,j)表示走到i,j格子时的最小路径。背包问题dp(i,j)表示装了第i个物品时背包还剩j空间时的最大价格。打家劫舍问题dp(i)表示打劫到第i个房间时的最大收益。这里只简单说明矩形问题与打家劫舍问题。矩形问题状态转移方程重点看上个状态是如何转移过来的。一般矩形只能向右或者向下移动路途可能有一些障碍物不能走我们要做分支判断然后选择一条符合题目最值要求的路线作为当前dp(i)的转移方程即可。打家劫舍问题由于不能同时打劫相邻的房屋所以对于dp(i)要么为了打劫i-1而不打劫第i间或者打劫i-2与第i间取这两种终态的收益最大值即可dp(i) max(dp(i-1), dp(i-2) coins[i])源码佐证矩形类 DP 的二维实现范式矩形类 DP 的二维实现范式可以参考仓库 算法/286.精读《算法题 - 地下城游戏》.md。该题中每个格子只能向下或向右移动所以dp[i][j]可以由dp[i-1][j]或dp[i][j-1]移动得到注意i或j为 0 时的边界场景因此判断从哪条路过来的最低初始 HP 最低即可const paths [] if (i 0) { paths.push([i - 1, j]) } if (j 0) { paths.push([i, j - 1]) }这正是上个状态如何转移过来的具体代码形态。同时该文也警示如果发现当前 DP 项居然可能由后面的值决定说明遇到了后效性导致无法使用 DP——此时需要换成从结果倒推的逆向思维从右下角开始才能保证动态规划的每个判断点都只考虑一个影响因素。这类正推失败、逆推成功的案例是理解无后效性特征最直观的进阶材料。总结动态规划三步法动态规划的核心分为三步定义清楚状态即dp(i)是什么。这是最容易忽略但最重要的一步参数定义对了状态转移方程往往就呼之欲出了仓库 算法/288.精读《算法题 - 编辑距离》.md 的总结也强调动态规划第一难点在于定义参数第二难点在于写状态转移方程而只要定义对了参数状态转移方程也就呼之欲出了因此最难的一步就是定义参数。定义状态转移方程这一步需要一些思考技巧例如连 or 断遍历所有前驱 j情况一分为二嵌套 DP多变量 DP等套路。思考验证正确性尝试证明你写的状态转移方程是正确的在这个过程要做到状态转移的不重不漏——所有情况都被涵盖了进来。动态规划最经典的还是背包问题由于篇幅原因可能单独成篇介绍。想继续深入二维动态规划与逆向思维的读者推荐继续阅读仓库中 算法/286.精读《算法题 - 地下城游戏》.md 与 算法/288.精读《算法题 - 编辑距离》.md 两篇配套题解。附录快速判定清单做题时遇到最优解类问题可以先跑一遍这张清单判定问题通过标准不通过时的替代方案存在最优子结构吗子问题最优解能推导全局最优解换定义方式或考虑贪心存在重复子问题吗同一子问题会被多处重复计算无缓存红利考虑回溯算法/200.精读《算法 - 回溯》.md无后效性吗前面选择不影响后续游戏规则尝试逆向思维消除后效性算法/286.精读《算法题 - 地下城游戏》.md或改用回溯版权声明自由转载-非商用-非衍生-保持署名创意共享 3.0 许可证。赞分享文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载相关推荐新手必看EMO-Ai-7b-Q8_0-GGUF快速入门指南与常见问题解答新手必看EMO Ai 7b Q8_0 GGUF快速入门指南与常见问题解答 EMO Ai 7b Q8_0 GGUF是一款基于Mistral架构的高效文本生成模型Hello 算法动态规划入门从爬楼梯看暴力搜索、记忆化搜索到状态转移方程Hello 算法动态规划入门从爬楼梯看暴力搜索、记忆化搜索到状态转移方程 本篇基于 《Hello 算法》动态规划章节的初探动态规划文档 https://l教程文档示例工程教育动态规划DP算法实战指南从状态定义到状态转移的完整解题框架动态规划DP算法实战指南从状态定义到状态转移的完整解题框架 动态规划Dynamic ProgrammingDP是算法学习中最重要也最考验思维的算法设教程上一篇微信单向好友检测终极指南三步快速识别谁偷偷删了你下一篇极域电子教室破解工具JiYuTrainer3步快速解除课堂控制限制创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考