动态规划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)它等于什么呢?按照我们刚才说的啊,它等于
这一大堆东西里面的最小的那个。最小的那个是什么呢?