大数据微课邹博详解动态规划

  烦请大家允许我先做个广告:这个是《面试算法》的课程内容,12次课,每次2小时,共24课时。课程中会给出所有算法的C/C++源码,以数据结构堆栈、队列、字符串、树、图的顺序系统阐述相关算法,同时分析动态规划、贪心法、分治法、回溯法、分支限界等诸多算法类别。

  课程内容将对笔试面试中的算法问题进行深入剖析,使大家在整体把握和细节分析的算法能力都得到加强。

  这是今天的主要内容,大概需要2个小时,主要形式是文字+PPT图片,而课件本身会在咱们微课结束后上传到小象学院网,大家到时候下载即可。

  大家等会在微课分享中,可以边看PPT截图,边结合我的文字,希望能够表达清楚。重要的事情再说一遍:一定要边看截图边看文字,文字是对PPT截图的解释说明。

  因为这也是我第一次使用微课这种形式做分享,如果有些考虑不周或者有问题的,随时告诉我就好。把非技术影响降到最低。好了,现在我们开始吧?

  大家或多或少知道“动态规划”“贪心法”这两个名词吧——或许已经非常熟练,或许模糊的有个印象;我个人喜欢用一个图示,从认识论的角度来对二者做个联系和区分。

  首先稍微上升到哲学高度,还记得哲学课上对于“认识论”的描述么?认识事物的方法有3个层次:基本认识、加深认识、高层认识,它们分别对应于“概念”、“判断”、“推理”。

  而“推理”中又可粗略的分为归纳法和演绎法。演绎是从一般到特殊的过程,属于汇聚思维;而今天我们重点考察归纳推理,它是从特殊到一般,属于发散思维。

  此刻,若将问题规模降低到0,即已知A0,很容易计算或证明B,即方便得到: A0[表情]B;

  同时,考察从A0增加一个元素,得到A1的变化过程。即:A0[表情]A1;

  此时,由于上述推导往往不是等价推导(Ai和Ai+1不是互为充要条件),导致随着i的增加,有价值的前提信息越来越少;为避免这一问题,采取如下方案:

  相对应的,修正后的方法依然是(严格的)归纳推理,有时被称作第二数学归纳法。

  这其实是咱们在高中数学课上学的,我只是又复述了一遍而已。我把第一数学归纳法和第二数学归纳法各画了个图。

  大家看,至此为止有问题吗?我们给出2分钟时间,大家现在可以用文字自由提问。

  *正是因为不方便直接得出结论,我们有时候才会逐层认识、慢慢解决问题的。*

  *必然,A0是长度为0的字符串,A1是长度为1的字符串。增加的元素,就是a[0]么~*

  观察第一数学归纳法:对于Ai+1,只需考察前一个状态Ai即可完成整个推理过程,它的特点是只要状态Ai确定,则计算Ai+1时不需要考察更前序的状态A1…Ai-1,我们将这一模型称之为马尔科夫模型;

  再看第二数学归纳法:相应的,对于Ai+1,需考察前i个状态集{A1、A2、……、Ai-1、Ai}才可完成整个推理过程,往往称之为高阶马尔科夫模型;

  重点来了:在计算机算法中,高阶马尔科夫模型的推理叫做“动态规划”,而马尔科夫模型的推理,对应“贪心法”。

  我们得到了对贪心法和动态规划一致性的理解,那么,这个模型对我们解题有何帮助呢?我们看一个经典的例子:最长递增子序列Longest IncreasingSubsequence,简称LIS。

  LIS问题的表述为:给定长度为N的数组A,计算A的最长的单调递增的子序列(不一定连续)。如:给定数组A{5,6,7,1,2,8},则A的LIS为{5,6,7,8},长度为4。

  这个定义本身,大家有什么问题没?有问题请提问,没问题的话,我们后面就来分析具体的算法,进一步完成代码实现。等待30秒。

  现在的问题是:计算长度为N的数组A的LIS,那么,A1、A2……应该是什么呢?

  因为子序列要求是递增的,所以重点是子序列的起始字符和结尾字符。那我们就可以利用结尾字符

  想到:以A[0]结尾的最长递增子序列有多长?以A[1]结尾的最长递增子序列有多长?……以A[n-1]结尾的最长递增子序列有多长?

  从而得到思路:如果有一个秘书,她已经帮我计算得到了i个整数b[0]、b[1]……b[i-1],(即:对于数组A[0...n-1],以A结尾的LIS的长度,我们是否可以利用这些信息,计算A[i]的LIS的长度呢?[/i]

  很简单,只需要比对一下字符“7”可以缀到候选字符串{“1”、“14”、“146”、“12”、“1468”、“14689”}中哪些的后面即可。

  显然,可以得到“17”、“147”、“1467”、“127”这4个递增序列;这4个序列最长的是“1467”,长度为4。所以,以“7”结尾的LIS是“1467”,长度为4。

  这个是LIS最重要的一个分析。仍然留出2分钟自由讨论。大家看,有什么问题么?

  *我的思路,就是要算B,但不知道怎么算,则分解成A0/A1/A2...An,然后逐个算*

  *一般不算。往往在做回溯法的时候,用提前剪枝的办法终止一些分支,加快搜索速度,这个问题,我们后面可以再谈*

  记A的前i个字符构成的前缀串为Ai= a[0]a[1]a[2]...a[i-1],以a结尾的最长递增子序列记做Li,其长度记为b;

  *原始数组不一定有序——一般都不是有序,但我们要找一个有序的,且最长的。*

  根据刚才具体例子的做法:如果将ai分别缀到L0 L1…… Li-1后面,是否允许呢?

  显然,如果ai[表情]aj,则可以将ai缀到Lj的后面,得到比Lj更长的字符串。

  根据这个式子,计算b的过程是:遍历在i之前的所有位置j,找出满足条件aj[表情]ai的最大的b[j]+1;

  计算得到b[0…n-1]后,遍历所有的b,找出b[0...n-1]的最大值即为最大递增子序列的长度。

  计算b需要i次查询,i的范围是0到n-1,所以,总的时间复杂度为O(N2)。

  事实上,通过记录“前驱”的方式即可:递推关系b={max(b[j])+1, 0[表情]j<i且aj[表情]ai}中,哪一个b[j]最大,则i的“前驱”即为j。记录下这个信息后,从n-1找到它的前驱,继续找前驱的前驱,从而一直到无前驱的元素,即得到了LIS本身。

  左侧的GetLIS函数是用来根据前驱恢复LIS本身的。大家课下可以思考下。

  有问题可以在我们的社区进一步讨论。当然,如果提问时能够at一下我的名字“visio”,我能够很快找到问题,答疑也会快很多。

  *机器学习我习惯用Python实现,算法我更多的使用C/C++,不过,实际工作我是用Java*

  *如果要得到所有解,需要用广度优先或者深度优先——我个人推荐用深度优先啦。*

  *这个多解性,可以暂时不作为重点;否则学习起来就枝蔓了。我到时候会以“中文分词”,“回文划分”等多个例子,来讲解如果要得到所有解,可以怎么写代码。*

  *算法的难度是:内容太多,如果跳跃性太强,容易每一个点都浮于表面,所以,大家稍微注意下深入理解算法的每个章节。*

  仍然选择刚才的数组A={1,4,6,2,8,9,7},我们递增式的选择元素,让每一次选的都尽量的小。什么意思呢?我们来实际操作一下:

  看到了字符“4”,“4”比缓冲区的所有字符都大,因此将“4”添加到缓冲区的最后,得到“14”;

  看到了字符“6”,“6”比缓冲区的所有字符都大,因此将“6”添加到缓冲区的最后,得到“146”;

  看到了字符“2”,“2”比“1”大,比“4”小,因此将“4”直接替换成“2”,得到“126”;

  看到了字符“8”,“8”比缓冲区的所有字符都大,因此将“8”添加到缓冲区的最后,得到“1268”;

  看到了字符“9”,“9”比缓冲区的所有字符都大,因此将“9”添加到缓冲区的最后,得到“12689”;

  看到了字符“7”,“7”比“6”大,比“8”小,因此将“8”直接替换成“7”,得到“12679”;

  其实,只是因为每次都把当前能够满足递增的最小字符放到缓冲区的合适位置即可。

  看到了字符“2”,“2”比“1”大,比“4”小,因此将“4”直接替换成“2”,得到“126”;这个是为什么

  大家会发现,这样的做法,每次都在一个递增的序列中插入新元素,所以总的时间复杂度是O(NlogN),同时,对于新字符的插入,只需要知道缓冲区的当前状态,不需要知道缓冲区更早的状态。因此,这种方法是贪心法。

  大家不妨继续思考:如果使用这种贪心的方法,如何计算LIS本身呢?时间所限,这个就当做思考题吧。——《面试算法》班

  从这个例子也可以看成:贪心法并不简单,动态规划也不是那么困难。大家看,有问题么?

  那,下面我们看另外一个经典的动态规划问题:格子取数,或者说:走棋盘问题。如何?

  *哦,对了,多说一句,如果在笔试面试的时候,知道O(NlogN)的算法,是可以留下很好的印象的。*

  我们现在进行另外一个经典的动态规划问题:格子取数,或者说:走棋盘问题。如何?

  问题描述是这样的:给定m×n的矩阵,每个位置是一个非负整数,从左上角开始放一个机器人,它每次只能朝右和下走,走到右下角,求机器人的所有路径中,总和最小的那条路径。

  现在思考一个问题:如果某时刻机器人位于(x,y)处,则它是从哪里来的呢?

  很显然,一般情况下,它有两个可能的来源:要么从(x-1,y)向右走一步,要么从(x,y-1)向下走一步。既然要找最小的路径,那么得到状态转移方程:dp[x,y] =min(dp[x-1,y]+a[x,y],dp[x,y-1]+a[x,y]),其中a[x,y]是坐标(x,y)处已知的棋盘权值。

  所以,两句线)首行和首列就是前n项和;(2)其他位置,比较(x,y)的左边和上边,哪个值小就用哪个做更新。

  观察这个状态转移方程发现,每次更新(x,y),只需要最多知道上一行即可,没必要知道更早的数据。凡是满足这样条件的动态规划问题,都可以用“滚动数组”的方式做空间上的优化——甚至有可能降低空间复杂度。

  *我们先把这个问题本身搞透彻,然后对这个问题会给出一个极其重要的实践应用的。*

  *每次更新(x,y),只需要最多知道上一行即可,没必要知道更早的数据。*

  *但笔试面试和实践中,有些情况,恰好不需要计算解本身,只需要知道解的某个性质就够了。*

  *是的,算法课中,必然要介绍一些实践常用,但教科书其实不怎么提的东西。*

  我在硕博期间是做计算几何方向的,我在实践中遇到了一个看似完全无关的问题,但本质就是刚才这个走棋盘问题。跟大家多聊两句。

  我的场景是:在三维空间中给定了两条折线(两条折线的拐点坐标都已知,一般情况是三维非平面的),现在要做的是:在空间中拟合一个曲面,要求这个曲面经过这两天折线,且拟合的这个曲面“最好看”。

  请原谅我用“最好看”这样的语言,但项目要求就是如此。所以,作为算法和软件实现者,第一步我需要定义什么叫“最好看”?

  大家再观察这个曲面,形成曲面的是若干三角形。我给出的想法是:要想形成某个曲面,则必然存在若干条连接两条折线的中间那些线段(截图中白色的线段),如果这些线段的总长度最短,我就认为“能量最低”,也就是所谓的“最好看”!

  有了“总和最短”这个目标,剩下的就好办了:这就是刚才我们讨论的走棋盘问题,内容完全一样。因此,我调用刚才的走棋盘的算法,就能够找到最短路径,进一步把相应的点用三角形做三维渲染,就得到了上面的截图。

  这显然是三维建模的核心问题之一,但内核只是一个只能往右和往下走的机器人罢了。是不是很简单?[得意]

  *因为折线形成的三位曲面,不能自交。如果允许往回走,则曲面就自交叉了。*

  *从算法上讲,存在多个解相同且都是最优的情况。但实践中出现的几率几乎是0——浮点计算长度,完全相当,太难了。*

  *即使多解,我随便挑一个就是了。反正他们都是最优解。对不对?何必要渴求所有呢,“君子有而不贪”,对不对?*

  *把算法搞透彻了,实现代码的过程,其实就是“哪里不会点哪里——So Easy”。*

  继续看刚才那个图片,如果是第一行或者第一列,则只能一路向右走或向下走——这个没太懂

  *因为,一旦某一次往下走了,因为不能回退,则不可能走到首行第5列的那个结点了*

  棋盘里 An是不是(x,y)和(A0,。。。,An-1)是(x-1,y)(x,y-1)呢?

  *我们的例子中是二维的,所以(x,y)有两个邻接点,大家不妨思考下,如果是N维,有几个临界点?——我知道,你已经get了,是不是?。。。。。。Yeah!*

  *多说一句吧,机器学习班中有一次课专门讲隐马尔科夫模型HMM,它的维特比(Viterbi)算法,就是这个走棋盘问题稍加推广而已。*

  *但矩阵链乘法的时间复杂度是O(N3)了,后面会给出算法和代码分析的。*

  *打个比方吧:老式的织布机有印象吧?梭子来回穿的那种。用一维的线怎么织成二维的布的?*

  *大家可能对滚动数组比较陌生,没关系,后面我们会持续给出非常多的例子,来练习这个技术的。*

  好的。我准备的最后这个题目是“找零钱问题”,它有个近亲,叫做“0/1背包问题”,二者其实本质是一样的。

  “找零钱问题”是这样描述的:给定某不超过100万元的现金总额,兑换成数量不限的100、50、20、10、5、2、1元的纸币组合,共有多少种组合?

  首先还是考虑最简单的情况:如果面额都是1元的,则无论总额多少,可行的组合数显然都为1。比如只用1元的纸币凑出100元,有几种方法?显然只有1种嘛:拿100张1元纸币就是了,别无他法。

  我们定义dp[j]:使用面额小于等于i的钱币,凑成j元钱,共有多少种组合方法。

  举个例子:dp[100][500],表示用面额小于等于100的钱币,凑出500块钱,有多少种不同的方法。

  可以这么思考:既然用小于等于100的纸币凑500块钱,则要么纸币组合中包含了100元纸币,要么没有包括100元纸币。

  *题目没有写错。给100万的上限,只是告诉大家,用int能够搞定,不必考虑大整数等枝蔓问题。*

  (1)如果没有包括100元,则用到的最大的可能面额是50元,即用小于等于50的纸币,凑500元,根据我们的定义,这个数字就是dp[50][500]

  (2)如果必须包括100元,怎么计算呢?既然必须有100元纸币的参与,则提前拿出一张100元纸币,则还需要再凑400块,那就是说,用小于等于100元的纸币,凑400块钱,有多少种组合方法呢?根据定义,就是dp[100][400]嘛!

  这里的状态转移方程不是严格表达,算是我们的思考的中间结果吧。i_small是指的比i小的那个纸币;如:i如果是100,则i_small就是50;i如果是20,则i_small就是10等等。

  如果“用小于等于100的纸币凑78元”,其实和“用小于等于50的纸币凑78元”是完全一样的。因为一旦用了100元,则超过了78元的总额。所以,如果jdom,dp[负数]是0。

  *首先还是考虑最简单的情况:如果面额都是1元的,则无论总额多少,可行的组合数显然都为1。比如只用1元的纸币凑出100元,有几种方法?显然只有1种嘛:拿100张1元纸币就是了,别无他法。

  这里是我写代码时的一个trick:为了保证方便,我认为,虚无的东西,本身就算1种。

  dp[100][500] 就是含有 dp[50][500](不考虑有100面额的组合情况) + dp[100][400](考虑有100面额的情况,但是400到500,只有再加一张100元的,但是组合数没变)所以可以看成这两种组合的加是这样理解吧?

  *菩提本无树,明镜亦非台。——等大家完全掌握了DP,再这么理解哈。——当然,我一定程度下统一这种说法。*

  别忘了,我们计算dp[j],其实最多只需要dp[i_small][j],而不需要更小的i_small。所以,这个状态转移方程仍然满足滚动数组的使用条件。

  *当然,现在各大公司招聘,都需要会算法。所以,功利的说,算个敲门砖吧。*

  另外,动态规划还有很多问题,如刚才的走棋盘问题,可以变化成“两次走棋盘问题”,或者“带陷阱的走棋盘问题”,这都是在一线和准一线的笔试面试中被问到的。PS,是S和A打头的两个公司。

  还有矩阵连乘问题、括号匹配问题,它们其实都和“Catalan数”有关,都可以用动态规划来解。今天讲了最长递增子序列LIS,还有最长公共子序列LCS、字符串编辑距离等,也是动态规划的内容,也是我们学习动态规划的很好的素材。

  另外,别忘了《面试算法》班,将系统的阐述算法的各个环节:堆栈/队列/字符串/树/图。

  算法班的内容经过了多次的迭代和更新,或许是全网最好的算法班了——我有这个信心。

  只要是IT的,都会问到。我把近年来大部分公司的大部分笔试面试题,都过了一遍。

  *有时候,说一个算法好,很容易;说一个算法不好,要有强有力的证据。呵呵。*

  *暂时不知道哈,这个是经典技术的,baidu/Google,应该都能搜到不少吧?*