dp总结--by fj.doc

动态规划总结 -By fj 动态规划，一种神奇的算法。搞了这么久的dp，我们从初识它，到理解它，到运用它，她那神秘的面纱逐渐被揭下。对它的理解：一种特殊的递推，一种剪枝的搜索。它分多阶段，状态转移只受前一状态影响。这期间，考了许多次考试，虽然考得不是很理想，但收获还是多多的。以下是部分题目的解法及心得体会 Stone （2.11上午）完成这题后，感触颇多！1解法的多样性。 法1）转移：fi，j表示将第i堆到第j堆石子合并所需要的最少代价； fi，j=fi，k+fk+1，j+wi，j； WI,j表示将这两部分石子合并的费用 （实为i到j的每堆石子的代价和，可预先处理gi表示从第1个到第i堆石子的代价和， 则wI,j = gj gi-1） 边界：fI,i+1 = gi+1-gi-1 目标：f1,n 复杂度：O（n3） 显然对于数据范围而言是出不来的。 法2）算法：从第一堆石子往后找，直到找到某堆石子的前堆石子数小于或等于其后堆石子数， 将这堆石子与前堆石子合并，得到新堆；从新堆处往前找，直到某堆石子数大于新堆石子数， 将新堆石子插入到这堆石子后面；重复以上操作直到只剩下一堆。 预处理：c0：=maxlongint； cn+1：=maxlongint； 数据结构：链表（记录+指针）； 2建立指针链接时，思路要清晰。 建立指针链接时，没开发的域为空； 例：new（p）； q:=p.next; 则q=nil。 故不能进行如下操作： p.ne:=p.next.last; 而应： new(pp); pp.last:=p; p.next:=pp. brush （2.11上午）看了解题报告后，其优化还是不懂，就选了未优化的算法。但是10000*10000的数组空间不够，我真是个傻子，此处可以轻易将第二维压缩，通过罗雨屏的指点，空间立刻压缩到10000*100!真神!罗雨屏咋就那么聪明呢? Brike （2.11下午）开始没做出来，看了孟来俊的总结（知识点杂新建文件夹（2）常用算法动态规划动态规划-孟来俊）和王准轩的程序后发现他们的算法有点不同，弄得我迷迷糊糊。最后综合两者的方法，自己编了一个，对了！方法：转化模型+动态规划；转化模型详见知识点杂新建文件夹（2）常用算法动态规划动态规划-孟来俊;方程：fi,j,k表示做到第i行，第j列，打了k个砖块，所得的最大价值。 if i=0 then fi,j,k=maxfi,j,k,fi,j-1,k,fi+1,j-1,k else fi,j,k:=max(fi,j,k,fi-1,j,k-i+si,j,fi+1,j-1,k);边界：f0，1，0：=0； f1，j，1：=a1，j；预处理：si,j:=ai-k,j+k (0=k=i-1); Bridge （2.13上午）这题比较容易。动规方程：fi:=mintj,i+fj-1;其中：j=i; Mj,imax; tj,i:=maxci,tj,i-1;不过，不用tj,i 而用vj，i更优；原因：Tj，i存的是实型数，占内存大；故用vj，i 跑的更快，空间更小。 Tree （2.13上午）设f(i,j)中序遍历为i,i+1,j的二叉树的最大加分，则有： f(i,j)=maxfi,k-1*fk+1,j +dk显然 f(i,i)=di答案为f(1,n)1=i=