文档介绍：动态规划总结专题一状态表示在用动态规划解题时,我么往往第一个考虑的是数组维数,其实数组维度(和状态表示)是有规律可循的::一般采用二位数组——d[i,j]表示当i,j为某一边角时的极值(e:d[i,j]可以表示以i,j为右上角时所能构成的正方形的边长最大值——听不懂?接着往下看)。还有一种表示方法:d[i,num]表示走到第i各阶段的第num个位置:1,12,23,34,45,56,62,13,24,35,46,57,53,14,25,36,47,48,44,15,26,37,38,39,35,16,27,28,29,210,26,17,18,19,110,111,1这种表示解决“多次访问同一图”类的DP题很有用。:这里指阶段划分十分明显的题(0/1背包)。一般采用d[i,j]表示执行到第i各阶段,剩余代价为j时,所能取得的最高分。(如果限制条件多,可增加维度)。:一般用d[i]来表示以i为根节点的最优值,可以加维来保证正确性。:这一类的DP最简单,是每一个OIER的必备基础,在这里就不废话了。专题二状态转移(专题二与专题一的分类标准不同,因为dugushuiyi说这样分更好,感谢他):d[i]=operation(d[j]+w[j,i])(w[i]为由j转移到i的消耗){operation为求最值}:d[i,j]:=operation(d[i-1,k]+w[k,j],d[i-2,……)如果只涉及到前面的有限个阶段,可以使用滚动数组。D[Imodn,j]=operation(d[(i-1)modn,k]+w[k,j],d[(i-2)modn,……):D[i,j]=max(d[lson[i],k1]+w[j,k1],d[rson[i],k2]+w[j,k2])遍历顺序一般为后序遍历顺序。:d[i,j]:=max(d[i-1,j]+w1,d[i,j-1]+w2)复杂度分析:DP的复杂度为:状态表示的数组维数*状态转移的代价SoA的复杂度为O(n^2)BCD:O(n^3);专题三题目分类总结一、一般类试题题库:最长不下降子序列最长匹配前缀邮票组合共性总结:1、题目一般可以通过for语句来枚举状态,所以时间复杂度为O(N^2)本类的状态是基础的基础,大部分的动态规划都要用到它,成为一个维。一般来说,有两种编号的状态:状态(i)表示前i个元素决策组成的一个状态。状态(i)表示用到了第i个元素,和其他在1到i-1间的元素,决策组成有的一个状态。二、01背包:(重点)★★★题库:01背包(USACO、vijos1025、1104)装箱问题(NOIP01Trade4)、取火柴问题(sgu153Playingwithmatches)共性总结:1、一般都从阶段的角度来表示状态2、因为d[i,j]只与d[i-1,k]有关,所以可以用滚动数组来实现。D[odd(i),j]各例分析:1、采药(NOIP2006、vijos)一个背包,每个物品只能放一次。(1)D[i,j]:=max(d[i,j],d[i,j-t[i]]+p[i]);D[I,j]表示决策了前i个物品,花费了j的代价优化:滚动数组