算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
几个例题
Loading...
Do curso por Peking University
算法基础
271 ratings
Na lição
动态规划（1）
通过上一模块的学习，你已经了解如何通过递归的办法解决问题，但是单纯的递归往往会导致子问题被重复计算，因此在解决某些问题的时候，效率会很低。而将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的方法就叫做“动态规划”。本模块将初步介绍对于特定的问题如何寻找子问题、定义问题的状态以及状态转移方程。
Conheça os instrutores
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
动态规划iii呢并没有一定iii，需要具体问题具体分析。
下面我们来看一个例题。
展开一下思路。一个是经典的这个最长公共子序列，
它说的是给出两个字符串，让你求一个这两个字符串都有的，
公共子序列的长度，求最大的一个长度， 然后这个序列里面呢每一个字符都能够在两个原串中找到，
而且每个字符的先后顺序跟原串中的顺序是一致的。
叫做公共子序列，要求最长的公共子序列的长度。
我们看一个例子，比如说这两个字符串，它们的最长的公共子序列是什么呢？
最长的公共子序列就是这个abc，一个串iii，
第二个串里面有abcd，所以abcd这个子序列
是他们的公共子序列而且是最长的，最长的是4，那下面这个programming和contest
这两个字符串它们的公共子序列有哪些呢？我们数出来一个o
n，子序列，o,n,对吧，而且它的长度是2，那你也找不到更长的子序列了，
所以这个，答案就是2.那下面这两个字符串，它们没有这个公共的子序列，所以答案就是0.
这是最长公共子序列。
它适合用动归来解决。
那我们有两个串，s1,s2， 我们用MaxLen(i,j)来表示
s1左边的i个字符形成的子串，
和s2左边的j个字符形成的子串它的最长公共子序列的长度，
我们的i.j都是从0开始算的，好，那当然这个时候i,j本身这个状态，
MaxLen(i,j)就是这个状态的值，那我们假设
s1的长度是len1，s2的长度是len2，那我们这个题目是不是就要求MaxLen(len1,len2) 对吧，这就包括了两个完整的情况。
那现在我们就要想办法递推的式子还有一些初始状态，是吧，
初始状态的有些 初始状态的值很容易确定的，比方说MaxLen(n,0)那肯定是等于0，
因为其中一个子串的长度等于0，那公共序列的长度肯定也是0，
那同样，MaxLen（0，n）它肯定也是等于0，这个
是毫无疑问的。当这个i.j都不为0的时候，
这个递推的关系就不是那么容易写出来了，
就可以仔细想一想了，怎么去想这个东西就不好说了。我们就说这个结果吧。
结果就说现在我们要求MaxLen(i,j)
MaxLen(i,j)就是s1的左边x字符所形成的的子串，
记作s1,
和s2左边的j个字符所形成的一个子串，把它记作s2，
j，ok，MaxLen(i,j)就说这两个子串的最长公共子序列的长度，
那我们怎么进行递推呢？我们就要考察这两个子串的最后一个字符，s1[i-1]和s2[j-1]， 因为s1最左边的字符是s1[0]，
类推，就这两个子串
他们最右边的那个字符，如果是相等的话，
那我们知道，这个MaxLen(i,j)它就等于MaxLen(i-1,j-1)+1
这是什么意思啊，MaxLen(i-1,j-1)是什么啊，
就是s1的i-1和s2这个j-1
这两个子串它们的 最长公共子序列的长度对吧，
由于这两个子串的最后一个字符是相同的，那么这两个子串的最长公共子序列的长度
我们在这两个子串的最长公共子序列的后面再加上
这两个子串的最后一个字符，当然就能够形成一个
更长的公共子序列，这个更长的公共子序列长度就增加了1， 所以当这个s1i和s2j
它们的最后一个字符相同的时候就可以是这样，
那如果这两个字符串它们的最后一个字符不相同的时候你可以是怎么样的呢？
你可以是这样，MaxLen(i,j)等于两者之间
更大的那一个。这个MaxLen(i,j-1)是什么，
是s1i和s2j-1这两个
字符串的最长公共子序列的长度。
而这个MaxLen(i-1,j)又什么呢，它是s1i-1和s2j
这两个
字符串的最长公共子序列的长度，然后我们这个MaxLen(i,j)呢就等于两者之间
更大的那个，那为什么是这样，等会再解释。我们先利用这样的iii的地推公式以后，
我们就知道，这个问题的时间复杂度是O(mn)的，
因为我们需要一个二维数组来存放这些MaxLen的值，而这个二维数组的元素个数当然就是两个字符串的乘积，
然后我们做动归的时候需要把这个二维数组便利一下，那整个问题的时间复杂度当然是O(mn)的，
下面我们要来证明这个递推式是
正确的。我们来看。这整个的是s1，
然后呢s1的最后一个字符当然是s1i-1，那它前面这个字串叫做s1i-1，
那s2在这，它最后一个字符是s2j-1，它前面这部分呢
叫做s2j-1,现在我们要下的一个结论就是 当这两个东西不相等的时候，MaxLen(s1,s2)
就是s1和s2的最长公共子序列的长度
它不会比这两者中间的任何一个小，
也不会比这两者都大，这个
MaxLen(s1,s2)j-1是什么，是s1这个字符串和
s2里面的这个字符串它所形成的最长公共子序列的长度，
那这个MaxLen(s1i-1,s2)就什么呢？就是
这个东西和整个的S2所形成的最长公共子序列的长度。
那现在我们下的结论是这个东西不会比这两者中间的任何一个
小，这是肯定的，因为 这两个串比这两个串要长，
那它们的最长公共子序列长度怎么反而会比他小呢，不可能，
那你要不太容易证明的是，这一项它不会比这两项的两者中间
不会比两者都大，为什么不会比两者都大呢？
那我们用反证法，我们先看这项，先假设这项
比这项大，意味着什么呢？就是这个
s1和s2形成的最长公共子序列它比
s1和这块s2j-1的这个形成的公共子序列要长，
那它这项为什么会比这项大呢？
我们看到，它肯定就是因为s2比s2j-1长，才会导致这项比这项大，
对吧，那s2比s2j-1长在什么地方呢？
它就多出来了，这个字符而已。因为多出来的这个字符，所以这项就比这项大，那说明什么问题啊，
说明这最后一个字符它一定 是s1和s2的最长公共子序列里面的那个字符，
它如果不是的话，那这项就没有理由比这项大，
对吧？好了，也就是我们证明了如果这项比这项大，那么
s2的最后一个字符，就一定会是s1和s2的最长公共子序列里面的
那个最后一个字符。那同理 如果这项比这项
要大的话，我们也可以证明，
s1的最后字符一定会是s1和s2的最长公共子序列里面的
字符，当然它也是最后一个字符，好，那也就说，
如果这项同时比这两项都大的话，
那么s1的最后一个字符，就会是s1和s2最长公共子序列里面的 那个字符，当然它是最后一个，s2的最后这个字符也会是
s1和s2的最长公共子序列里面的那个字符，当然也是最后一个，
那这样的话那肯定s1的最后一个字符它就必须等于s2的最后一个字符了，
这就跟我们前面假设的那个两者不等是矛盾的了。
所以通过这个反证法我们就能够证明这一项它一定不会同时比这两项 都大，好了。
这项不同时比这两项都大，而且它又不比这两项中间的任何一项
要小的话，那这项应该等于什么呢？当然就是这两者之间
更大的那个。所以说我们就
证明出来了上面这个例子的这个式子。
那这个程序动归的写法写起来的话就是
iii它们的第一行和第一列全部都是0，
然后我们要从这边开始推算这边某一个
i,j的MaxLen的值的时候怎么办呢？这个值有可能是它上方的斜上方的那个值，再加1，
也可能是它正上方的那个值，
和它左边的那个值两个里面取一个大的，这个就是
递推的过程，那我们基本上的程序呢就是在这块
就做一个初始化，然后接下来是一个两重循环，是这个
m*n的，在这两重循环里面做了这个递推，这我们就不细讲了。
好，看下一题。
啊总之呢我们做动归的时候呢，每一道题目具体都是不一样的，所以我们一定要在掌握
递归和动归思想的前提下，然后我们要具体问题具体去进行分析，解决问题的时候灵活运用这些技巧。
下一个题，叫做"Help Jimmy"啊。
很好玩的一个题目啊。它说的是一个游戏，啊这个东西呢黑点
是一个老鼠，它叫Jimmy。然后这个老鼠下面有好多个板子，现在这个老鼠呢它想要
跳到地面上，啊然后再回到家里去，问题是它
跳下的距离如果太高的话，就会摔死。所以它得从一块板一块板子往下跳，啊。
嗯 老鼠在时刻0，它从高于所有平台的某处开始下落
然后下落的速度是每秒1米。它落到某个平台以后，它就会
你可以让它向左跑，也可以让它向右跑，它跑动的速度也是每秒1米。
它跑到平台边缘的时候，它可能就会自然掉下来了，啊。
它就会掉下来，然后掉到板子上还可以接着跑，那Jimmy每次下落的高度不能超过MAX 要不然它就会摔死，摔死了游戏就结束了。
呃现在要让你设计一个程序，计算Jimmy到地面 它最少要花多长时间。
嗯，那我们就只讲思路啊，具体的程序就不做了，要怎么做输入输出，输出的数据我们也，也不管它了。
那现在我们怎么思考这个问题呢？就是说Jimmy它跳到一块板子以后
它实际上有两种选择对吧？它可以往左边跑，也可以往右边跑。
那落到一块板子以后，它跑到左端和跑到右端的
时间那是很容易算出来的，就是它的到左端和右端的距离，对吧？
它有两种选择，那到底往左端好跑，就是往左端跑好还是往右端跑好呢？
那如果我们已经算出来Jimmy从左端这个点往下掉 能够到地面的最短时间。
如果我们也算出来从右端这个点往下掉，到地面的最短时间。
如果这两项我们都算出来了，那我们取一个小的，往那个方向走不就得了，对吧？
所以我们现在就进行了这个子问题分解了。我们分解出来的子问题实际上跟原来那个问题的形式是一模一样的。
只不过被分解成了两个子问题 对吧？就是，就是它，它首先得跳到第一块板子上，跳到第一块
板子上以后呢，它可以往左也可以往右，那左右两端各是一个子问题，就变成两个子问题。
那这个子问题的形式跟原来是 原来的问题是一模一样的。
啊，那这个时候我们分解完子问题以后，我们就要算这个
确定这个状态，到底是什么是状态呢？首先我们要确定，诶，到底什么东西是跟状态有关的那个变量？
那我们可以把板子从1，从上到下
从1开始排序，啊进行无重复的这个编号，那越高的板子我们让它编号越小，高度相同的几块板子，哪块
编号在前哪块在后无所谓。那这个时候呢，呃
跟，跟具体问题相关的那个变量，实际上也就是
这个板子的编号，因为你要求的就是，呃从一个板子上它的左端到地面的时间和
右端到地面的时间，那这个板子的编号是跟问题，跟这个子问题相关的，对吧？
也就是说跟子问题相关的变量就一个，就是这个板子的编号了。
那我们可以认为Jimmy一开始从一个编号为0的，长度为0的板子往下掉
然后我们可以利用一个LeftMinTime(k)表示从k号板子的左端到地面的最短时间，用RightMinTime(k)
表示k号板子的右端到地面的最短时间。
那这个时候我们求板子k左端点到地面最短时间的方法是什么样的啊？
注意左端点啊，我们可以写出这个递推的过程，啊。
Jimmy从板子k的左端点要往下掉，那如果 板子k的左端正下方它没有别的板子，那它就会直接掉到地上。
那直接掉到地上的话它下落的高度就是h(k)，h(k)就是第k号板子的这个高度。
那如果h(k)它大于这个Jimmy所能允许下落的最大高度的话 那么这个时候Jimmy就没有办法回到家里了。
它没法跳到地上，所以LeftMinTime(k)=∞。
否则的话呢，那LeftMinTime(k)当然就等于h(k)
对吧？它就直接跳到地上了，然后它要花的时间就是 就是下落的时间，就是h(k)，因为每秒下落1米嘛。
好，这说的是板子k左端没有
左端正下方没有别的板子了。那如果板子k的左端正下方 它有一块板子，然后这个编号是m，那你怎么办呢？那就跳到
这个编号为m的板子上，对吧？那跳到编号为m的板子上它所需要花的时间是多少啊？
啊是h(k)-h(m),就是两个板子的高度差。现在我们要计算的是
LeftMinTime(k)，就是说从板子k的左端落到地面所需要的最短时间。
那我们把时间分成部分，把它加起来，第一部分就是落到板子m所需的时间 就是下落的时间。
然后呢落到板子m上以后呢，我们就得要考虑到底是往左边走
还是往右边走的，对吧？那往左边需要花多少时间呢？ 呃，那当然就是
LeftMinTime(m)，因为我们要走到板子编号，编号为m的板子左边，然后就要从这个
左边往下掉了，那么左，左边往下掉到地面的最少时间是多少呢？当然就是LeftMinTime(m)对吧？
那往左走的话我们还要再加上一个走到左端所需的这个时间，这走到左端所需的时间我们是
Lx(k)-Lx(m)。
这Lx(k)是什么呢？就是第k号 板子它左端点的这个横向的这个坐标。
那Lx(m)就是第m号板子它的左端点的这个横向的，水平方向的这个坐标。
那两者的差呢就是两个端点的距离对吧？这，这老鼠必须走过这个距离，所以它要加上这个时间。
啊，那要从右端走的情况呢就是这个啦，啊就是
呃，RightMinTime(m)，就是从m号板子右端掉到地面最短的时间，再加上我们
落到m号板子以后往右端走所花的时间，那就是Rx(m)-Lx(k)。
Rx(m)是m号左，m号板子右端点的那个横坐标，呃两者之差 是水平走动所需的这个时间。
那有了这样的一个初始，有了这样一个递推式，啊我们当然就可以把程序写出来啦。
呃这里面需要注意的就是这个，这当然我们还要
求RightMinTime(k)对吧？这个RightMinTime我们要求出来，它的求法跟 求，求LeftMinTime是类似的。
那我们就可以认为Jimmy开始的位置就是一个编号为0，长度为0的板子，然后它从左端往下跳。
那这个整个问题就是要求LeftMinTime(0)。
嗯，要注意的是这个输入数据这里面啊 这个板子它并没有按照高度排序，所以我们这个程序一定要把
板子先给它按高度排好序。那我们这个程序你可以用
递归，记忆式的递归来实现，也可以用这个
递推的方法，比如说是“人人为我”的这个递推的方法来做都是可以的。
那时间复杂度是什么样的呢？因为一共有n块板子，然后每，每块板子左右两端各算一遍，啊那所以
这个计算的就是，次数一共就是0(n)的。
但是我们在计算，呃，从某一端掉到地面的时间的时候呢，我们会需要找到这个端点下方
到底有哪个板子？那这个找板子的过程就需要把其他板子都
看一遍。所以，找板子就需要0(n)的时间。
啊因此总的时间复杂度就是两项乘起来，就是0(n2)。
这个就是我刚才说的简单做法的这个情况下就是0(n2)。
当然你要找板子，也许你可以找到什么办法去优化一下，让时间复杂度也有可能的，啊下降。
那具体的程序呢我们就跳过去 就不说了啊。查查我们写出来的两种程序就是
呃记忆递归型和这个“人人为我”的递推型，啊。
下面我们再看一道叫做“最佳加法表达式”。
它说的是有一个由1到9组成的数字串。
它问如果将m个加号插入到这个数字串中
那就会形成一个加法表达式，对吧？那它要问的是在各种可能形成的表达式里面
值最小的那个表达式的值是多少？就是它形成加法表达式以后，比如说算出的加法把它们都加起来
然后就可以得到一个和，那值最小的那个和，这样一个表达式它的值是多少。
大家想一想，然后再接着看解答。
这种呢，看上去就像一个递归的题，关键是你得要
能想出子问题，能够确定状态，才能想出状态之间转移的这个，这个iii。
那我们首先就进行这个子问题的分解，啊，我们可以假设数字串的长度是n
那我们要添加一大堆的加号，对吧？
那我们就假设我们添加完加号以后，最后一个加号添加在
第i个数字的后面，最后一个就是最右边的那个加号啦，它被添加在第i个数字的后面。
那这个时候，我们在确定第i个
确定最后一个加号，被添加在第i个数字后面的这个前提下，它前面还有
m-1个加号可以有各种各样的这个放法对吧？
那不管怎么样，这时候整个表达式的最小值就等于在前面的i个数字中我们插入m-1个
加号所能形成的最小值，再加上
那个最后一个加号，右边的那些数字所形成的那个整数。
也就是第i+1到第n个数字所组成的那个整数。
这两者之和就是整个表达式的这个，这个最小值啦。
因此，我们解题思路就是这样，我们用
V(m,n)表示在n个数字中插入m个加号所能形成的表达式的最小值。
那我们先看边界条件啊，就是初始条件。那如果m=0， 就是说根本就没有加号需要放，
那V(m,n)就等于什么啊？就等于这n个数字所组成的那个整数，它的这个数值。
那还有一种情况，就是说，如果n<m+1，
你要放m个加号，那每个加号边上，两边都得有数字，对吧。那肯定数字得
有m+1个数字才行。那如果数字的数目比m+1要小的话，
实际上你就不可能成功地放入这个加号。就是说这时候
你已经没法放加号了，那么V(m,n)的值我们就认为是无穷大。等于说V(m,n)这种方案，它是不可行的，那它的这个
值我们取无穷大，就排除掉这种方案被使用。
那除了这两种边界条件以外，我们就可以写出递推的式子，就是
V(m,n)它等于什么呢？按照我们刚才说的啊，它等于
这一大堆东西里面的最小的那个。最小的那个是什么呢？
这一项它当然表示的就是我们把最右边的那个加号，放到第i个数字的 右边，也就是后边。
在这种情况下，所能形成的这个最佳加号表达式的这个
最小值，对吧。那么这个Num(i+1,n)，
就是第i+1个数字到n， 这些数字之间的这些数字所能拼出来那个整数。
那第i+1个数字就是最后一个加号右边的那个数字了，对吧。
最后一个加号放的位置，当然你不能从0开始放，你肯定得从 第m个数字的右边，
才能往后，才能才能放。那这个V(m-1,
i)当然就是说，我们把最右边的那个加号放好了，那还剩下m-1个加号。
让它放在前面的i的数字之间。
对吧，所能形成的最佳加法表达式的那个最小值就是V(m-1, i)，然后这个是整个的，
把加号放在，最右边的加号放在第X最后面的这个情况。
然后我们在这么多种方法里面，选一个最优的。也就是说我们先枚举了
最右边那个加号的放法。然后在各种最右边加号方法里面选一个最优的，
就是这个意思。那么这样一个问题，它的时间复杂度是什么样的呢？
那我们知道有这样一个二维数组，
是吧，这个二维数组，我们对于m,n的每种组合都要算一下。那这时候，时间复杂度就是，
m乘以n的，对吧。那我们在具体算一个V(m,n)的时候， 我们还需要去算这一项。
这一项就是若干个数字排在一起，所组成的那个整数，它到底是多大，对吧。那算这一项的话，你得把
这个组成那个整数的所有数字都看一遍。
那一共有多少个数字啊？一共有n-i-1+1这个数字，对吧。它的量级也是
o(n)的，所以我们这时候整个问题的时间复杂度还要再乘一个n。
所以整个问题的时间复杂度就 是O (mn2)，对吧。那具体的程序呢，我就不给出来了。
在这里，我们关键就是要讲讲思路。希望思路对大家有启发作用，程序大家自己回去编写。
好，再看下一个例题，叫做滑雪。它在百练上面，是1088。
Michael喜欢滑雪啊，我也喜欢滑雪，因为确实很刺激。
那你滑雪当然只能从高的地方往下滑，不能从低的地方往上，往高的地方滑，对吧。
那我们假定有一个滑雪场，
是一个矩形，这个矩形上面每一个点就代表
滑雪场上面的一个位置。
每个点都代表一个位置，这个位置的高度就是这个矩阵上面的一个数字。
那我们要滑雪的话，我们就得选一个点，然后就
从高往低滑，那滑雪大家都希望能够滑的距离长一点，对吧。
所以呢，你选一个什么样的初始点， 往下滑，你能滑到的距离最长。就是一个对滑雪者特别有意义的这个，这个题目了。那我们在这个题目里的规定，滑雪者只能
如果只能站在这，那他就只能往 左右上下四个方向滑，而且这四个方向必须，
就是说其中有一个方向，它的位置是比你现在站的这个位置低，你才能够滑下去。
那好了，现在我们在这个问题里面，一个可能的滑行路径是， 24 17 16 1，对吧，就是从24开始，滑到17，再滑到16，再滑到1.
这是一条路线，但是它太短了。
那最长的路线是什么呢？实际上应该是这样，25到24到23，到22,21这样绕一圈这样滑，
这个时候滑行的距离就是25，就是你站立的地方也算是距离的一部分。
这样的话，你现在滑行的距离就是25。那我们的问题就是，你能 得到的最长的滑行距离是多长？
给定一个这样的高度矩阵，问你 能得到的滑行距离是多长？
这输入就是这样一个高度的矩阵啊。
在这种情况下，最长距离是25。那怎么做呢？ 这也是一个一看就觉得很像一个典型的这个递归，或者说动规的问题。
递归的问题往往也可以转化成动规的问题。那考虑问题的方式就是
挺简单的啊，就是，我们用L(i,j)表示从点(i,j)出发的最长滑行长度。
那我们肯定能够写出一些初始的这个
值了，对吧，或者说边界的值。就是说，如果一个点(i,j)，它周围没有比它更低的点，所以周围就是上下左右。
那在这种情况下，L(i,j)就等于1。
周围没有比它更低的点，它滑不动。所以L(i,j)就是1,。否则的话，我们就用递推公式了。
就是跟数字三角形很像的，对吧。你就在(i,j)周围找比它更低的点。
比它更低的点可能有好几个，你到底选哪一个合适呢？你当然选从那个点出发， 它已经能得到滑行距离最长的那个点，对吧。
所以递推公式就是L(i,j)，它等于(i,j)周围四个点中，
比L(i,j)低，首先肯定得比L(i,j)低了，且L值最大的那个点的L值，再加上1，
值就呈现出来了，对吧。那这个问题的时间复杂度就是O(n2)。
因为整个矩阵一共有n平方个点，是吧，所以就是O(n2)。
哪个点，滑进去，只需要算一次。
那要解决这个问题呢，
如果写递归，是比较好写的。如果写递推的话，这里面就会有一个问题，就是递推嘛，都是从
已知推出未知，对吧。那哪些是已知的呢？这个推导的顺序到底怎么做呢？
我们前面看到的一些例子，一般来说，比如说这个状态是用一个二维数组表示。
然后我们就一行一行地递推，或者说一列一列地递推，但是在这个问题里面， 这个递推的顺序好像有点奇怪，它没法，
从上一行推到下一行，或者从左边这一列推到右边那一列。他们这个推的顺序好像挺随机的。
那我们可以确定一点，递推的顺序就是，在一个 矮的点，它的这个L值还没有求出来的情况下，
那比它高的相邻点的那个L值，是不可能真正被求出来的，对吧。
所以说，我们就可以想，这个递推的顺序应该是什么啊？应该是从矮到高。
那么很直观的，我就可以把所有的点，按照高度，从小到大进行排序。
那这里呢，我可以把每个点的L值都初始化成1。这个是
没有问题的，对吧。因为每个点出发点至少可以就走站立的那个点。它的长度，
滑行长度至少就是1。我们把所有点按照高度从小到大排序以后呢，我们就从小到大遍历所有的点。
然后我们经过一个点的时候，我就用递推公式去求L(i,j)。
那我们要用递推公式，求这个L(i,j)的时候， 我们会用得到和点(i,j)相邻的，也就是上下左右的，
而且高度低于点(i,j)的那些点的L值。
那这些点的L值是不是都已经求出来了呢？答案是肯定的。
因为我们事先已经将所有点按照高度从小到大排序了。
而且我们遍历的时候，也是从小到大遍历所有的点。
那也就是说，当我们到达点，遍历到点(i,j)的时候， 那些所有高度低于点(i,j)的那些点，我肯定都已经走过了。
走过了，就意味着它的L值就已经被求出来了。
所以这个时候，我们要求点(i,j)的L值的时候，
所有比它低的那些点的L值，我们都已经具备，那我们就可以使用这个递推公式了。
好那这里，这是人人为我的这个形式的这种递推，实际上还有我为人人这种形式的递推，也能解决 这个问题。
那前面都是一样的，初始化成1，然后所有的点按高度从小到大排序，然后也是从小到大遍历所有的点。
只不过在经过一个点(i,j)的时候，这个
点(i,j)的L值我们就认为已经求出来了。为什么我们可以认为已经求出来了呢？
就是因为我们在经过一个点(i,j)的时候，我会用当前这个点(i,j)的值， 去更新它周围的比它高的那些L值。
那我们这个遍历当然就是从这个最低点开始的，对吧？最低点的L值，它首先就已经求出来了，就是1。
那这里所说的更新，到底怎么更新呢？ 就是假设现在我遍历到这个点(i,j)，
然后点(i,j)的高度是H(i,j)。那此时我认为点(i,j)的L值，它是已经求出的。
然后我要用点这个(i,j)的L值，去更新
(i,j)这个点周围的一些点的L值。
什么样的点的值，L值，有可能被更新呢？就是在(i,j)周围，
而且高度高于点(i,j)的那些点的L值是有可能被更新。我们假定
点(i,j)的右边那个点，当然就是 我下面这个点吧。就是(i+1j)。假设
点(i,j)下面的那个点(i+1j)，它的高度是大于(i,j)的高度的。
那我们就要试图去更新，这个(i+1j)这个点的L值。
怎么更新呢？我们知道这个时候，我们可以推断
点(i+1j)这个点的L值啊，它起码可以是 L(i,j)+1，对吧。
因为它可以往高再走一步，那就相当于我们从(i+1j)起码你还可以滑到这个
(i+1j)。那(i+1j)的L值再加上1就是 L(i+1j)至少的这个值了，最低的这个值了。
但是这个L(i+1j)这个值有可能已经通过其他手段被更新过了。说不定它更新完以后，比你这个值还要大。
所以说我们当然就，要在这两者之间取一个max就可以解决了。
所以这就是，我为人人方式的递推，就是我们
已经知道了一个点，(i,j)的L值的时候，我要去更新 跟这个点相关的，其他一些点的L的值。
还是再说明一下，为什么我们 到达，遍历到一个点(i,j)的时候，我们认为这个点的L值就已经求出来了呢。
这是因为，比如说你到达了一个点，(i,j)在这，那它周围另外有两个点。
这两个点呢，都比你这个(i,j)这个点要低，对吧。
作为这两个点，肯定比(i,j)这个点要先，那它
先被遍历，那它们被遍历过的时候，它们的L值，肯定L1，L2就都已经求出来了，对吧。
那我们知道，在遍历这两个点的时候，它们都分别用自己的
L值去更新了，你(i,j)这点的L值。这点 用这点的L值去更新(i,j)值的时候，
(i,j)的值至少就会是L1+1，对吧。那我们用这点的L值
L2去更新(i,j)这点L值的时候，(i,j)这点的L值，它至少就会是
L2+1，对吧。那我们这个点嘛，假设它
周围比它低的点只有这两个， 那也就是说，你从这个点往下滑，你要么就往这边走，要么就往这边走。
然后它的L值，它要么就是L1+1，要么就是L2+2，实际上是两者之间更大的那个，对吧。
那所以我们就知道，这两个点走完以后，由于它们都采用了更新，对这个点进行更新，所以这个点的
L值就已经确定了，要么就是L1+1，要么就是L2+2。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
