计算机解决问题没有奇技淫巧但动态规划还是有点套路.docx

计算机解决问题没有奇技淫巧，但动态规划还是有点套路|labuladong来源|labuladongID:labuladong【导读】动态规划算法似乎是一种很高深莫测的算法你会在一些面试或者算法书籍的高级技巧局部看到相关内容什么状态转移方程重叠子问题最优子构造等高大上的词汇可以能让你望而却步。而且当你去看用动态规划解决某个问题的代码时你会觉得这样解决问题竟然如此巧妙但却难以理解你可能惊讶于人家是怎么想到这种解法的。实际上动态规划是一种常见的算法设计技巧并没有什么高深莫测至于各种高大上的术语那是吓唬别人用的只要你亲自体验几把这些名词的含义其实显而易见再简单不过了。至于为什么最终的解法看起来如此精妙是因为动态规划遵循一套固定的流程递归的暴力解法-带备忘录的递归解法-非递归的动态规划解法。这个经过是层层递进的解决问题的经过你假如没有前面的铺垫直接看最终的非递归动态规划解法当然会觉得牛逼而不可及了。当然见的多了考虑多了是可以一步写出非递归的动态规划解法的。任何技巧都需要练习我们先遵循这个流程走算法设计也就这些套路除此之外真的没啥高深的。以下先通过两个个比拟简单的例子斐波那契以及凑零钱问题揭开动态规划的神秘面纱描绘上述三个流程。后续还会写几篇文章讨论怎样使用动态规划技巧解决比拟复杂的经典问题。首先第一个快被举烂了的例子斐波那契数列。请读者不要嫌弃这个例子简单因为简单的例子才能让你把精力充分集中在算法背后的通用思想以及技巧上而不会被那些隐晦的细节问题搞的莫名其妙。后续困难的例子有的是。步骤一、暴力的递归算法PS但凡遇到需要递归的问题最好都画出递归树这对你分析算法的复杂度寻找算法低效的原因都有宏大帮助。这个递归树怎么理解就是讲想要计算原问题f(20)我就得先计算出子问题f(19)以及f(18)然后要计算f(19)我就要先算出子问题f(18)以及f(17)以此类推。最后遇到f(1)或f(2)的时候结果已知就能直接返回结果递归树不再向下生长了。递归算法的时间复杂度怎么计算子问题个数乘以解决一个子问题需要的时间。子问题个数即递归树中节点的总数。显然二叉树节点总数为指数级别所以子问题个数为O(2n)。解决一个子问题的时间在本算法中没有循环只有f(n-1)f(n-2)一个加法操作时间为O(1)。所以这个算法的时间复杂度为O(2n)指数级别爆炸。观察递归树很明显发现了算法低效的原因存在大量重复计算比方f(18)被计算了两次而且你可以看到以f(18)为根的这个递归树体量宏大多算一遍会消耗宏大的时间。更何况还不止f(18)这一个节点被重复计算所以这个算法及其低效。这就是动态规划问题的第一个性质重叠子问题。下面我们想方法解决这个问题。步骤二、带备忘录的递归解法明确了问题其实就已经把问题解决了一半。即然耗时的原因是重复计算那么我们可以造一个备忘录每次算出某个子问题的答案后别急着返回先记到备忘录里再返回每次遇到一个子问题先去备忘录里查一查假如发现之前已经解决过这个问题了直接把答案拿出来用不要再耗时去计算了。一般使用一个数组充当这个备忘录当然你可以以使用哈希表字典思想都是一样的。如今画出递归树你就知道备忘录到底做了什么。实际上带备忘录的递归算法把一棵存在巨量冗余的递归树通过剪枝改造成了一幅不存在冗余的递归图极大减少了子问题即递归图中节点的个数。递归算法的时间复杂度怎么算子问题个数乘以解决一个子问题需要的时间。子问题个数即图中节点的总数由于本算法不存在冗余计算子问题就是f(1),f(2),f(3).f(20)数量以及输入规模n20成正比所以子问题个数为O(n)。解决一个子问题的时间同上没有什么循环时间为O(1)。所以本算法的时间复杂度是O(n)。比起暴力算法是降维打击。至此带备忘录的递归解法的效率已经以及动态规划一样了。实际上这种解法以及动态规划的思想已经差不多了只不过这种方法叫做自顶向下动态规划叫做自底向上。啥叫自顶向下注意我们刚刚画的递归树或讲图是从上向下延伸都是从一个规模较大的原问题比方讲f(20)向下逐渐分解规模直到f(1)以及f(2)触底然后逐层返答复案这就叫自顶向下。啥叫自底向上反过来我们直接从最底下最简单问题规模最小的f(1)以及f(2)开场往上推直到推到我们想要的答案f(20)这就是动态规划的思路这也是为什么动态规划一般都脱离了递归而是由循环迭代完成计算。步骤三、动态规划有了上一步备忘录的启发我们可以把这个备忘录独立出来成为一张表就叫做DPtable吧在这张表上完成自底向上的推算岂不美哉画个图就很好理解了而且你发现这个DPtable十分像之前那个剪枝后的结果只是反过来算而已。实际上带备忘录的递归解法中的备忘录最终完成后就是这个DPtable所以讲这两种解法其实是差不多的大局部情况下效率也根本一样。这里引出动态转移方程这个名词实际上就是描绘问题构造的数学形式为啥叫状态转移方程为了听起来高端。你把f(n)想做一个状态n这个状态n是由状态n-1以及状态n-2相加转移而来这就叫状态转移仅此而已。你会发现上面的几种解法中的所有操作例如returnf(n-1)f(n-2)dpidpi-1dpi-2和对备忘录或者DPtable的初始化操作都是围绕这个方程式的不同表现形式。可见列出状态转移方程的重要性它是解决问题的核心。很容易发现其实状态转移方程直接代表着暴力解法。千万不要看不起暴力解动态规划问题最困难的就是写出状态转移方程即这个暴力解。优化方法无非是用备忘录或DPtable再无微妙可言。这个例子的最后讲一个细节优化。细心的读者会发现根据斐波那契数列的状态转移方程当前状态只以及之前的两个状态有关其实并不需要那么长的一个DPtable来存储所有的状态只要想方法存储之前的两个状态就行了。所以可以进一步优化把空间复杂度降为O(1)有人会问动态规划的另一个重要特性最优子构造怎么没有涉及下面会涉及。斐波那契数列的例子严格来讲不算动态规划以上旨在演示算法设计螺旋上升的经过。当问题中要求求一个最优解或者在代码中看到循环以及max、min等函数时十有八九需要动态规划大显身手。下面看第二个例子凑零钱问题有了上面的详细铺垫这个问题会很快解决。题目给你k种面值的硬币面值分别为c1,c2.ck再给一个总金额n问你最少需要几枚硬币凑出这个金额假如不可能凑出那么答复-1。比方讲k3面值分别为125总金额n11那么最少需要3枚硬币即11551。下面走流程。一、暴力解法首先是最困难的一步写出状态转移方程这个问题比拟好写其实这个方程就用到了最优子构造性质原问题的解由子问题的最优解构成。即f(11)由f(10),f(9),f(6)的最优解转移而来。记住要符合最优子构造子问题间必须相互独立。啥叫互相独立你肯定不想看数学证明我用一个直观的例子来讲解。比方讲你的原问题是考出最高的总成绩那么你的子问题就是要把语文考到最高数学考到最高.为了每门课考到最高你要把每门课相应的选择题分数拿到最高填空题分数拿到最高.当然最终就是你每门课都是总分值这就是最高的总成绩。得到了正确的结果最高的总成绩就是总分。因为这个经过符合最优子构造“每门科目考到最高这些子问题是相互独立互不干扰的。但是假如加一个条件你的语文成绩以及数学成绩会相互制约此消彼长。这样的话显然你能考到的最高总成绩就达不到总分了按刚刚那个思路就会得到错误的结果。因为子问题并不独立语文数学成绩无法同时最优所以最优子构造被破坏。回到凑零钱问题显然子问题之间没有互相制约而是相互独立的。所以这个状态转移方程是可以得到正确答案的。之后就没啥难点了按照方程写暴力递归算法即可。画出递归树时间复杂度分析子问题总数x每个子问题的时间。子问题总数为递归树节点个数这个比拟难看出来是O(nk)总之是指数级别的。每个子问题中含有一个for循环复杂度为O(k)。所以总时间复杂度为O(k*nk)指数级别。二、带备忘录的递归算法不画图了很显然备忘录大大减小了子问题数目完全消除了子问题的冗余所以子问题总数不会超过金额数n即子问题数目为O(n)。处理一个子问题的时间不变仍是O(k)所以总的时间复杂度是O(kn)。三、动态规划最后总结假如你不太解析动态规划还能看到这里真得给你鼓掌相信你已经掌握了这个算法的设计技巧。计算机解决问题其实没有任何奇技淫巧它唯一的解决方法就是穷举穷举所有可能性。算法设计无非就是先考虑“怎样穷举然后再追求“怎样聪明地穷举。列出动态转移方程就是在解决“怎样穷举的问题。之所以讲它难一是因为很多穷举需要递归实现二是因为有的问题本身的解空间复杂不那么容易穷举完好。备忘录、DPtable就是在追求“怎样聪明地穷举。用空间换时间的思路是降低时间复杂度的不二法门除此之外试问还能玩出啥花活*本文为AI科技大本营转载文章转载请联络精彩推荐2019中国大数据技术大会BDTC历经十一载再度炽热来袭豪华主席阵容及百位技术专家齐聚15场优选专题技术以及行业论坛超强干货技术剖析行业理论立体解读深化解析热门技术在行业中的理论落地。【早鸟票】与【特惠学生票】限时抢购扫码解析详情推荐浏览