搜索
算法基础动态规划动态规划解决的问题•在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。动态规划的一般过程描述最优解的结构（找出状态）递归定义最优解的值（列出状态转移方程）按自底向上的方式计算最优解的值由计算出的结果构造一个最优解什么是动态规划先讲一下什么是记忆化搜索记忆化搜索Fibonacci数递推公式为：Fib[n]=Fib[n-1]+Fib[n-2],已知Fib[0],Fib[1]都是1,求Fib[n]的值1123581321…记忆化搜索•细想了之道题之后，由于f(n)=f(n-1)+f(n-2)，可写出以下程序来求解f(n)•intFib(intn)•{if(n2)return1;returnFib(n-1)+Fib(n-2);•}记忆化搜索但是，用这种方法，效率是比较低的，因为Fib(5)计算时需要计算Fib(4)和Fib(3)，而Fib(4)计算时又要重复的递归计算Fib(3)的值，这样，将会导致有许多重复的计算量。我们便想到了一种避免重复计算的方法，将计算过的值记录到一个数组中，下次计算的时候直接读出计算过的值而不是再递归计算该值。比如此题：constintMAX=40;intF[MAX]={1,1};intFib(intn){if(F[n])returnF[n];returnF[n]=Fib(n-1)+Fib(n-2);}•我们也可以从前往后的计算出Fib(n)的值•intF[MAX]={1,1};//前两项赋值为1•for(inti=2;in;i++)•F[n]=F[n-1]+F[n-2];•这样，计算出F[n]的值就是要求的值了，没有进行多余的计算•（看到这里之后，大家可以试着到OJ上把Fibonacci数和超级阶梯两道题给做了）•严格意义上的动态规划•刚才的题目里，从某种意义上已经具有了动态规划的一个基本特征，但不能算是严格的动态规划，动态规划有两个基本的特征：•一、重叠子问题•二、最优子结构•刚才的问题具有重叠子问题这个特征，那什么叫做最优子结构呢？•我们再看下面一道题：吃金币游戏•Zyc无聊时候写了一个简单的吃金币游戏，规则如下：•在一个长方形地图上，玩家每次能从一个方格走到相邻一个方格。•玩家控制的角色可以向下或者向右走，但不能向上或向左走。•每个方格上都有一定的金币。•现在，Zyc想请你帮他想一个策略，尽可能多的获得金币。•一些同学可能会说这道题使用搜索可以做出来。•没错，如果数据范围很小，这题题用搜索确实可以做出来，但是，如果数据范围很大呢？比如m=n=1000。•这时，使用搜索的方法要搜索C(1000,500)种情况，毫无疑问，用这种方法来计算的话，在我们有生之年恐怕算不结果出来了。•那么，这应该如何计算？用动态规划一般思路求解该题•我们意识到如果用F[a][b]表示达到(a,b)这个点时所能吃到的最大金币数量，F[a][b]的值只与F[a-1][b],F[a][b-1]这两个值有关。•（此步即为动态规划的第一步：描述最优解的结构，确定状态）•得到递推关系式：F[a][b]=max(F[a-1][b],F[a][b-1])+Coin[a][b]•（此步即为递归定义最优解的值，列出状态转移方程）•然后，根据该状态转移方程式，很轻松的可以确定出F的计算顺序，可以自底向上的计算出F的值（程序见下页）•如果题目要求计算出一条最优的路径，则可以用另一个数组Path来记录每次最优解选取子问题时的过程，最终通过数组Path还原出最优解。（即由计算出的结果构造一个最优解）intf[MAX][MAX],c;for(inti=1;i=m;i++)for(intj=1;j=n;j++){scanf(%d,&c);f[i][j]=max(f[i][j-1],f[i-1][j])+c;}最优子结构性质•可以看出，父问题的最优解依赖于一些子问题的最优解。•这就是所谓的最优子结构性质。看到这里，大家可以回去把OJ上的18题(TheTriangle)171题（聪明的kk），这道题给AC了，练习练习。最大连续子串和给定一整型数列{a1,a2...,an}，找出连续非空子串{ax,ax+1,...,ay}，使得该子序列的和最大，其中，1=x=y=n。•先确定状态，如果设F[n]表示前n个数中能选取出的最大连续子串和，则列出动态转移方程比较困难，列出方程的话复杂度也比较高。•如果用F[n]表示，以第n个数为结尾的最大连续子串和,则F[n]=max(F[n-1],0)+a[n]•再求出F[n]数组中的最大值就即为所求的最大连续子串和。•写出程序如下：最大连续子串和maxsum=-INT_MAX;scanf(%d,&m);for(inti=1;i=m;++i){scanf(%d,&a[i]);if(a[i-1]0)a[i]+=a[i-1];if(a[i]maxsum)maxsum=a[i];}printf(%d\n,maxsum);LCS最长公共子序列•最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（LongestCommonSubsequence）。其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。•现在给你两个序列，请你求出其最长的公共子序列。•比如：•1,2,3,4,5,6,2,1,1,17,8,9,10•1,3,4,6,3,54,6,34,3,2,1,7•这两个序列的最长公共子序列就是134621，长度为6动态规划的一般过程描述最优解的结构（找出状态）•思考：定什么为本题的状态？•定它为状态之后是否便于书写状态转移方程，该状态转移方程的时间复杂度是否合适？LCS如果定义F[m][n]表示A数组的前m个元素和B数组的前n个元素的最长公共子序列的长度。则可得以下的状态转移方程：如果A[m]==B[n]则F[m][n]=F[m-1][n-1]+1否则F[m][n]=max(F[m-1][n],F[m][n-1])由此，即可自底向上的解了F[m][n]的值按自底向上的方式计算最优解的值递归定义最优解的值（列出状态转移方程）•在计算最优解的过程中，可以用另外一个二维数组来表示每次选择，用c[i][j]=1表示result[i][j]是由result[i-1][j-1]得来的，用c[i][j]=2表示result[i][j]是由result[i-1][j]得来的，由c[i][j]=3表示result[i][j]是由result[i][j-1]得来的。•根据c数组的值，可以倒着从最后一步步推出每步的选择，进而确定出公共子序列中的元素。由计算出的结果构造一个最优解LIS•LIS:最长单调递增子序列•比如1,2,10,5,6,8,12,5这个序列的最长单调递增子序列是1,2,5,6,8,12•请思考该如何表示该题的最优解结构，即如何定义状态？•确定过状态之后，请思考动态转移方程式是什么？•F[m]表示以第m个元素为结尾的最长单调递增子序列的长度。则状态转移方程：f[m]=max{f[k]}+1其中k=0,1,2,...m-1，并且需要满足a[k]a[m]求解顺序之前的题目，都是很简单的很自然的便可确定求解的顺序，但，很多的时候是我们要确定出正确的求解顺序方可得出正确的答案：如下：NYOJ10滑雪•Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子•12345•161718196•152425207•142322218•131211109•一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。•如果设DP(m,n)表示坐标为从(m,n)点起始，能够达到的最长链。•则可知DP(i,j)的值为四周高度比(i,j)点底的点的DP值中的最大值+1.•即•DP(i,j)=max{DP(i,j-1),DP(i,j+1),DP(i-1,j),DP(i+1,j))}+1;•可是，这样一来，便可以清楚的看出，需要先算出较低的点的DP值，然后根据较低点的DP值可以算出较高点的DP值。•则此题的做法就明了了，先对所有的点的高度进行排序，然后按高度一个一个的按照状态转移方程进行计算即可。•此题便需要我们按从低较方的顺序求解方可得出答案。••#includeiostream•#includeset•#includeiterator•usingnamespacestd;•constintMAX=110;•structNode•{•Node(intx,inty,inth):x(x),y(y),h(h){}•intx,y,h;•};•booloperator(constNode&n1,constNode&n2)•{•returnn1.hn2.h;•}•intmain()•{•//freopen(D:\\1.txt,r,stdin);•intn;•cinn;•while(n--)•{•intdirection[4][2]={{-1,0},{0,-1},{1,0},{0,1}};•multisetNodest;•introw,col,h;•cinrowcol;•intresult[MAX][MAX]={0};•intheight[MAX][MAX]={0};•for(inti=0;i!=MAX;i++)•{•for(intj=0;j!=MAX;j++)•{•height[i][j]=-1;•}•}•for(inti=1;i=row;i++)•for(intj=1;j=col;j++)•{•cinh;•st.insert(Node(i,j,h));•height[i][j]=h;•}•intmaxnum=0;•for(multisetNode::iteratorit=st.begin();it!=st.end();++it)•{•result[it-x][it-y]=1;•for(inti=0;i!=4;i++)•{••if((result[it-x][it-y]result[it-x+direction[i][0]][it-y+direction[i][1]]+1)&&height[it-x][it-y]height[it-x+direction[i][0]][it-y+direction[i][1]])•result[it-x][it-y]=result[it-x+direction[i][0]][it-y+direction[i][1]]+1;•maxnum=max(maxnum,result[it-x][it-y]);•}•}•coutmaxnumendl;•}•}•在求解顺序难以确定的时候，可以使用记忆化搜索的方法。01背包问题•给定n种物品和一背包。物品i的重量是wi,其价值为vi，背包的容量为c，问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？•f[w][m]表示现在选取重量不超过w,在前m个物品中选取时，可获得的最大价值。•则f[w][m]=max{f[w-wi][m-1]+vi,f[w][m-1]