动态规划专题讲义

*,单击此处编辑母,版,文本样式,第二层,第三层,第四层,第五层,单击此处编辑母,版,标题样式,动态规划专题讲义,前言,本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,有不足和缺漏之处请谅解和及时地指出,.,动态规划,是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱,.,动态规划,目录,什么是动态规划,状态 阶段 决策,一种确立状态的方法,两种简单的动规武器,三种特殊的动态规划,什么是动态规划,在,学习动态规划之前你一定学过搜索,.,那么搜索与动态规划有什么关系呢,?,我们来下面的一个例子,.,back,数字三角形,给你一个数字三角形,形式如下,:,1,2 3,4 5 6,7 8 9 10,找出从第一层到最后一层的一条,路,使得所经过的权值之和最小或,者最大,.,back,数字三角形,无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：,f(i, j)=ai, j + minf(i-1, j)+f(i-1, j + 1),对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。,解决方法：,back,记忆化搜索,记忆化搜索,我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程,:,f1:=f(i-1,j+1); f2:=f(i-1,j);,if f1f2 then f:=f1+ai,j else f:=f2+ai,j;,显而易见，这个算法就是最简单的搜索算法。时间复杂,度为,2,n,，,明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个,opt,数组：,back,记忆化搜索,Opti, j -,每产生一个,f(i, j),，将,f(i, j),的值放入,opt,中，以后再次调用到,f(i, j),的时候，直接从,opti, j,来取就可以了。,于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的,.,记忆化的功效,back,动态规划的实质,可以看出动态规划的实质就是,这也就是为什么我们常说动态规划必须满足重叠子问题的原因,.,记忆化,正符合了这个要求,.,记忆化搜索,状态 阶段 决策,或许有一种对动态规划的简单称法,叫分阶段决策,.,其实我认为这个称法并不是很能让人理解,.,那么下面我们来看看阶段,状态,决策这三者间得关系吧,.,back,状态 阶段 决策,状态是表现出动态规划核心思想的一个东西,.,而分阶段决策这个东西有似乎没有提到状态,这是不科学的,.,阶段,有些题目并不一定表现出一定的阶段性,.,数字三角形的阶段就是每一层,.,这里我们引入一个概念,-,以前状态,.,但阶段不是以前状态,状态是阶段的表现形式,.,数字三角形的以前状态就是当前层的前一层,.,那什么是决策呢,?,我们看看下面一张图就知道了,.,back,决策,当前状态,以前状态,决策,显然,从上图可以看出,当前状态通过决策,回到了以前状态,.,可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。,数字三角形的决策就是选择相邻的两个以前状态的最优值。,back,动规的要诀状态,我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。,我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。,back,拦截导弹,拦截导弹（,Noip2002,）,某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统 有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高 于前一发的高度。 某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以 只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。,拦截导弹,状态的表示,fi,，,表示当第,i,个导弹必须选择时，前,i,个导弹最多能拦截多少。,每个导弹有一定的高度，当前状态就是以第,i,个导弹为最后一个打的导弹。以前状态就是在这个导弹以前打的那个导弹。,显然这是十分能够体现状态间的联系的题目。,back,最长公共子串,给出两个字符串序列。求出这样的一个最长的公共子串：子串中的每个字符都能在两个原串中找到，而且每个字符的顺序和原串中的顺序一致。,交错匹配,交错匹配（最长公共子串的改编）,给你两排数字,只能将两排中数字相同的两个位置相连,而每次相连必须有两个匹配形成一次交错,交错的连线不能再和别的交错连线有交点,.,问这两排数字最多能形成多少个交错匹配,.,2 3 3 2 4 1 5 1 3 5 10,3 1 2 3 2 4 12 1 5 5 3,状态的表示,fi,j,表示前,i,个第一排的数字和前,j,个第二排的数字搭配的最优值。,当前的状态就是当前你枚举到的一组交错的后面两个位置,.,例如上图中当前状态是,3,和,1(,第一组交错,),枚举他的以前状态就有,1 3.,这样在,1 3,之前会有一个最优值存在,因此可以由此得到,3 1,的最优值,.,back,买车票,买车票,(Ural1031),Ekaterinburg,城到,Sverdlovsk,城有直线形的铁路线。两城之间还有其他一些停靠站,总站数为,N,。,各站按照离,Ekaterinburg,城的距离编号。,Ekaterinburg,城编号为,1,，,Sverdlovsk,城编号为,N,。,back,买车票,某两站之间车票价格由这两站的距离,X,决定,.,当,0X=L1,时，票价为,C1,元,.,当,L1X=L2,时，票价为,C2,元,.,当,L2X costpij + cj) then costi:=costpij+cj;,end;,end;,back,动规的要诀状态,有时候当前状态确定后,以前状态就已经确定,则无需枚举,.,back,Tom,的,烦恼,Tom,是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用有限的资金开了一家汽车零件加工厂， 专门为汽车制造商制造零件。由于资金有限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他加 工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开始和结束时间相同不算冲突）。,Tom,当然希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件的加工时间要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得尽量多的加工费，,Tom,不知如何进行取舍。,Tom,的烦恼,Tom,的烦恼,按结束时间排序，枚举结束时间作为当前状态,以前状态就是该结束时间对应的起始时间，这是已经确定的,.,back,文字游戏,文字游戏,(,fairfox,邀请赛,1),给你一份单词表，和一个句子。求出该句子能有多少中不同的划分方法,.,例如,:,单词是,ab,cd,a b c d,句子是,abcd,他共有,4,种,完全,划分方案,:,ab/cd,a/b/c/d a/,b/cd,ab/c/d,;,当前状态就是单词在句子中向后靠的位置,以前状态就是确定这个单词位置以后,除掉这个单词长度后的一个位置,.,状态转移方程是,:Fi:=Fi+Fi-length(wordj),IOI,中有一题,前缀,也是类似的题目,.,决策中的定量,状态转移方程的构造无疑是动态规划过程中最重要的一步,也是最难的一步,.,对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量,.,定量处理的过程也就是决策实施的过程,.,寻找定量,back,寻找定量,最佳加法表达式,有一个由,1.9,组成的数字串,.,问如果将,m,个加号插入到这个数字串中,.,使得所形成的算术表达式的值最小,.,Problem,或许你不明白我在说什么,那么我们通过题目来说明吧,back,最佳加法表达式,这一题中的定量是什么呢,?,因为是添入加号,那么添完加号后,表达式的最后一定是个数字串,这就是定量,.,从这里入手,不难发现可以把以前状态认为是在前,i,个字符中插入,k-1,个加号,(,这里的,i,是当作决策在枚举,),然后,i+1,到最后一位一定是整个没有被分割的数字串,第,k,个加号就添在,i,与,i+1,个数字之间,.,这样就构造出了整个数字串的最优解,.,而至于,前,i,个字符中插入,k-1,个加号,这又回到了原问题的形式,也就是回到了以前状态,所以状态转移方程就能很快的构造出来了,.,back,最佳加法表达式,用,fi,j,表示的是在,前,i,个字符中插入,j,个加号能达到的最小值,最后的答案也就是,Flength(s),m.,于是就有一个动规的方程,: Fi,j:=min(fi,j,fk,j-1+numk+1,i) numk+1,i,表示,k+1,位到,i,位所形成的数字,.,这里显然是把加号插入了第,k+1,个位置上,.,知道了这一题怎么做以后,乘积最大的一题也是完全一样的形式,谁还会去用搜索,?,back,定量,现在大概大家已经了解了定量是什么,那么我们下面通过几道题目来了解一下定量的威力,.,back,游戏,游戏,(Noip2003,普及组,),这一题的描述简单说一下,:,在一个圈的周围,有,n,个石子,将他们划分成,m,堆,(,每堆中的石子必须连续相邻,),每一堆石子计算出他们的总重量,mod10,的值,然后将这些值相乘,求得到的结果最大最小值是多少,.,back,游戏,这一题作者其实是根据最佳加法表达式改编的,.,但是他加了一个在圈上的条件,怎么办呢,?,寻找定量,!,back,游戏,可想而知,因为至少要分成,1,堆,那么至少有两个石子之间是会被分隔开的,.,这就是定量,!,当划分数,1,时,一定有两个相邻石子被划分到不同的堆里去,!,于是这个圈被这样的理解断成了一条线,解法就和最佳加法表达式一样了,.,当然这个断开的位置是需要枚举的,然后保留下一个最优值,.,显然这个断开的操作对整个过程没有影响,因为这是必然的情况,这是定量,!,back,最优三角形划分,问题描述,给定一具有,N,（,N50,）,个顶点,(,从,1,到,N,编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成,N-2,个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？,back,最优三角形划分,这一题大概搜都是十分麻烦的,可是这一题,Dp,的话,比搜索要容易实现和容易理解得多,.,先得表示一下状态,我们用,fi,j,表示以第,i,个点开头,顺时针长度为,j,的一块子多边形,.,如上图中,f1,5,表示的子多边形,(,黑色虚线划开,),back,最优三角形划分,如果没有红色虚线的部分,或许你会认为决策应该是枚举子多边形内的两点连线,然后分成两个子多边形,.,这显然是不行的,因为计算机已经无法再表示分割出来的子多边形了,(,不能,用,fi,j,来表示了,).,back,最优三角形划分,那么我们该如何决策呢,?,寻找定量,!,显然可以发现,fi,j,表示的子多边形有一条边是在内部的,(,黑色虚线,),而这一条边在该子多边形内必定属于某个三角形,因为我们选择了该子多边形作为一种状态,那么就一定存在那条虚线黑边,所以一定存在所说的三角形,.,于是我们枚举这个三角形的另外一个点在子多边形的位置,则可以把子问题还原到原问题,(,因为该三角形把多边形划成了两个可以用表示的多边形和一个三角形,).,这些再次分割出的子多边形就是以前状态,而刚才的多边形则是当前状态,.,back,定量,其实定量的作用就是为了写出状态转移方程,即让人能迅速找出状态之间的关系,(,决策,).,通过定量的处理,当前状态又回到了以前状态,选手就可以知道,这一题就是要用动态规划来求解了,.,back,定量,我们来看看刚才的一些题目的定量,.,交错匹配,:,一定存在最后一组交错,(,这好像是废话,),所以枚举这个最后的交错的位置作为状态,这样就回到以前状态,.,买车票,:,定量,1:,一定有最后一个车站,(,这个作为状态,);,定量,2:,某个车站一定是由某个前面的车站到达的,.(,导弹拦截也是这样,),数字三角形,:,某个点一定是由他上面的相邻两点到达的,.(,过河卒也是这样,),定量很不错啊,!,动态规划的武器,在动规的操作过程中,或者是操作过程前,有一些很常用的武器,这里简要介绍两种,:,排序,填鸭,back,排序,武器一,:,排序,遇到过很多需要排序的动态规划题目,如果不排序,动规的思想很难体现,.,back,Tom,的烦恼,Tom,的烦恼,这是大家熟知的一题,如果不排序的话,复杂度便是,N2,按起始时间排序复杂度也是,N2,二按结束时间排序之后复杂度降为了,NlogN,.,back,巴比伦塔,巴比伦塔,问题描述,:,有很多的不同种类的立方体,(,长宽高不同,),每一类有无限多个,.,将他们一层层的叠加起来,要求上面的一块立方体的下底面一定要比下面的一块立方体的上底面要小,就是长和宽都要小于,.,问最多能建成多高的塔,.,back,巴比伦塔,经过研究可以发现,每一种类的立方体有,3,种不同的摆放方式,而每种摆放方式最多用,1,次,所以可以分离,出,3*N,块“不同”的立方体,接下来,或许你仍然不知道如何动规,那么就试试排序,.,列出所有的石块的所有摆放方式,xi,yi,zi,.,必须全部保证,xi,yi,.,然后按关键字,xi,yi,zi,的大小顺序排序,.,这样就可以进行十分简单的类似与导弹拦截的一个动态规划的处理了,.,限制条件是,xi,和,yi,代价值,是,zi,(,高度,).,back,滑雪,滑雪,(,上海,2002),题目的大意是给出一个矩阵,如,:,对于所给出的矩阵找出一条最长的递减链,满足链中相邻的两个元素间都是在矩阵中相邻的,.,上图中所给出的矩阵中的最长链,是,1 2 3 425.,back,滑雪,对于有给出的数字进行递减排序,然后两重循环就搞定问题,.,动态转移方程是,:,Fi:=max(Fi,Fj+1);,满足条件是,i,与,j,在原矩阵中相邻,.,试想,如果你不知道要排序,你能想到这题是用动态规划吗,?,back,填鸭,武器二,:,填鸭,这个思想带有枚举的感觉,.,就是开个大数组,把代价值一个个填进去,.,back,硬币问题,硬币问题（经典问题）,就是给出,n,种硬币的面值,问面值,M,有多少种不同的表示方法,.,动态转移方程是,Fi:=Fi+FI-costj.,当前状态是,i,以前状态是,i-costj.,多米诺骨牌（某题的简化）,有,N,张多米诺骨牌,每张的两端有两个数字,范围在,1.6,之间,.,每张骨牌可以正放,也可以反放,.,求出一种摆放的情况,使得所有的骨牌上端数字之和与下端数字之和的差值最小,.,求出最小差值,.,back,多米诺骨牌,可以这么考虑这个问题,:,我们把每一个骨牌的上下差值记,下。接下来的任务便是将这些值,分成两组，使得他们的和的差值,最小。动规过程如下：,f0:=true;,for i:=1 to n do,for j:=sum,downto,ai do,fj:=fj or fj-ai;,Sum,表示所有差值的和,. ai,表示第,i,块骨牌,的差值,. J,是,当前状态,j-ai,是,以前状态,.fj,表示,j,这个差值能否通过组合得到。,接下来的程序就不用我多说了。,back,商店购物,商店购物,(IOI),这一题更是需要开一个五维,bool,型数组,.,还需要通过递归求出组合形式,.,动规的方程我就不写了,.,back,动态规划的武器,讲完了比较实用的两种种动规的武器之后,我们来看看一些大家可能不太会做的动规类型,特殊的动规,这里我讲讲三种特殊的动态规划,:,图状动规,树状动规,二次动规,.,back,图状动规,城堡,某国聪明美丽的公主要找一位如意郎君，她希望未来的夫君是一个聪明善良，节俭但又不吝啬的人。为了找到理想的人选，她的爸爸,国王，给她修建了一座城堡，这个城堡有很多房间，房间之间有走廊连接，但每进入一个房间必须要花费一定数量的钱币，公主就在某个房间中等待。开始，国王给每个候选人一样多的钱币，候选人从同一个地点出发，直到找到美丽的公主为止，如果这时哪个人找到了公主，并且钱币刚好用完，那么他将会赢得公主的芳心。,back,城堡,乍看此题,似乎就是搜没得说了,是吗,?,如果告诉你这一题是动态规划的话,你会怎么做,?,状态是什么动态转移方程是什么,?,back,城堡,既然是问我们能不能到达,所以想想就应该知道,动规的数组是,bool,型的,.,一开始时,只有出发的房间记,为,true.,但是,并不是以每个房间作为状态,因为还存在一个把钱用光的问题,.,到达同一个房间时,如果剩余的钱不一样,也就会有不同的决策,.,所以状态就是在剩余,j,个钱币的时候能否到达第,i,个房间,.,用,fi,j,来表示,.,back,图状动规,于是动态转移方程也就出来了,fi,j:=fi,j or fk,j+ci,K,表示的是和,I,连接的一个房间,ci,表示进入,I,号房间的花费,.,back,树状动规,没有上司的晚会,某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的上司，要不然他们会很扫兴。现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人来能使得晚会的总活跃指数最大。,back,没有上司的晚会,按照要求构建一张关系图，可见这是一棵树。对于这类最值问题，向来是用动态规划求解的。,任何一个点的取舍可以看作一种决策，那么状态就是在某个点取的时候或者不取的时候，以他为跟的子树能有的最大活跃总值。分别可以,用,fi,1,和,fi,0,表示。,back,没有上司的晚会,当,这个点取的时候，他的所有儿子都不能取，所以,fi,1:=sum(fj,0,j,为,i,的儿子,),i,的权值。,不取的时候，他的所有儿子取不取无所谓，不过当然应该取价值最大的一种情况。所以,fi,0:=sum(max(fj,1,fj,0),j,为,i,的,i,儿子）。,这就是树状动规的基本形态。,back,二次动规,在,动规的基础上再进行动规，就叫做二次动规。,买票,有一座,n,层的楼房，某个人要到第,n,层的任何一个房间买票。每层楼都有,m,个房间。而如果要到第,i,层的第,j,个房间买票，那么必须先在第,i-1,层的第,j,个房间买票或者在第,i,层的与这个房间相邻的房间买过票才行,.,而每个房间所要收取的票费是不同的,给定每个房间内买票需要的费用,问要在第,n,层的任意一间房间内买到票的最小消费是多少,.,back,买票,显然不能写这样的状态转移方程,:fi,j:=min(fi-1,j,fi,j-1,fi,j+1)+wj.,因为无法有一种处理顺序使得在,fi,j,之前同时求得,fi,j-1,和,fi,j+1,的最优值,.,所以动规分两次进行,.,第一次用状态转移方程,fi,j:=min(fi,j-1,fi-1,j)+wi,求出一个不一定是最优的解,.,再,用,fi,j:=min(fi,j,fi,j+1,j from m-1,downto,1)+wi,求出最终的最优解,可以证明这样的能够求出真正的最优解,.,要注意的是这两次动规不能分开做,而要在处理每一层的时候都要做,要不然显然无法求得最优值。,back,综合题,网络（,Ural1056,求树的中心）,题目大意是：,有一棵有,N,个结点的树，给出每个结点的父亲（即给出这棵树），边的权都是,1,。每个结点延树的边可以走到树的任意一个结点，令,Ai,为第,i,个结点最远能走的距离，求出,Ai,最小的结点有哪些。如有多个最小的,Ai,，,则都要输出。这里,N=10000,back,网络,枚举每个点，然后,DFS,复杂度,O(N,2,),，,超时是显然的事情。,可以发现其实有很多,DFS,都重复做了同样的工作，产生了浪费，所以应该选择动态规划解决这个问题。,树上的,动规，是否直接可以写出下面的状态转移方城呢？,fi:=max(fson,ffather)+1,废话，显然是不行的，,son,和,father,的值不可能同时得到。,但是不要放弃，解决这个冲突的方法，就是采用二次动规。,back,网络,第一次动规做,fi:=max(fson)+1,，,第二次动规做,fi:=max(fi,ffather + 1),。,但是存在一个问题就是如果,ffather,的值是从,i,那里得到的，这样计算显然就错了。,不要放弃，在实际操作过程中，,f,需要记下两个值，一个是最优值，一个是次优值，这两个值必须由不用的子结点得到。这样当最优值发生矛盾的时候，次优值一定不会矛盾。问题就解决了。复杂度,O(N),十分的理想。,back,总结,动态规划有很多东西还需要我们更加努力地去探索和学习,.,总体上说来,动态规划是个既简单又不简单的算法,熟练地掌握了动态规划,也就熟练地控制了比赛,.,back,Thats all!,Thank you for listening.,back,动规练习题,垃圾陷阱（,USACO&TJU1087,）,卡门,农夫约翰极其珍视的一条,Holsteins,奶牛,已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为,D (2 = D = 100),英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间,t(0 t = 1000),，,以及每个垃圾堆放的高度,h(1 = h = 25),和吃进该垃圾能维持生命的时间,f(1 = f = 30),，,要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续,10,小时的能量，如果卡门,10,小时内没有进食，卡门就将饿死。,动规练习题,字符串距离（,TJU1086,）,设有字符串,X,，,我们称在,X,的头尾及中间插入任意多个空格后构成的新字符串为,X,的扩展串，如字符串,X,为“,abcbcd,”,，,则字符串“,abcbcd,”,，“,abcbcd,”,和“,abcbcd,”,都是,X,的扩展串，这里“,”,代表空格字符。 如果,A1,是字符串,A,的扩展串，,B1,是字符串,B,的扩展串，,A1,与,B1,具有相同的长度，那么我们定义字符串,A1,与,B1,的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的,ASCII,码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值,K,，,空格字符与空格字符的距离为,O,。,在字符串,A,、,B,的所有扩展串中，必定存在两个等长的扩展串,A1,、,B1,，,使得,A1,与,B1,之间的距离达到最小，我们将这一距离定义为字符串,A,、,B,的距离。 请你写一个程序，求出字符串,A,、,B,的距离。,动规练习题,二叉苹果树（,Ural1018,）,有一棵苹果树，如果树枝有分叉，一定是分,2,叉（就是说没有只有,1,个儿子的结点）这棵树共有,N,个结点（叶子点或者树枝分叉点），编号为,1-N,树根编号一定是,1,。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有,4,个树枝的树,2 5 / 3 4 / 1,现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。,动规练习题,最长前缀,IOI96&,USACO 1.4.3,）,在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。如果一个集合,P,中的元素可以通过串联组成一个序列,S,，,那么我们认为序列,S,可以分解为,P,中的元素。并不是所有的元素都必须出现。举个例子，序列,ABABACABAAB,可以分解为下面集合中的元素：,A, AB, BA, CA, BBC,序列,S,的前面,K,个字符称作,S,中长度为,K,的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。,动规练习题,祝福（,TJU1078,）,得知,Atlantis,即将沉没的消息以后，,King,决定把他的人民送到安全的国外去。但是码头已经废弃很多很多年了。码头前有一个迷宫，国王的骑士只身闯入了这个迷宫,骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作战，所以很快便招架不住了，他的大马被打得奄奄一息（。）这个时候，迷宫中的两座石像,(,一个是猫老大，一个是天使。（！,),里放出了无数锋利的刀片，把不明生物全部杀死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上多了一个戒指，上面写着： “这个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每次移动如果是只要,|x-x1|+|y-y1| (x1, y1),的移动！”,(Angel,暗自想：还有这么心黑的,),迷宫为,n*m,的矩阵。骑士从,(n, m),到,(1, 1),。问：在戒指的帮助下，骑士最少要多少步才能回到入口？在步数最少的前提下，总共有多少种办法到达入口？注意，骑士不会傻到一直停留在原地不动。,