下载文档原格式
第6章 动态规划动态规划（Dynamic Programming ）是解决多阶段决策过程最优化的一种有用的数学方法。
它是由美国学者Richard .Bellman 在1951年提出的，1957年他的专著《动态规划》一书问世，标志着运筹学的一个重要分支－动态规划的诞生.动态规划也是一种将多变量问题转化为单变量问题的一种方法。
在动态规划中，把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。
动态规划是考察解决问题的一种途径 ,而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法（如单纯形法）.事实上，在运用其解决问题的过程中还需要运用其它的优化算法。
因此，动态规划不像其它方法局限于解决某一类问题,它可以解决各类多阶段决策问题。
动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。
在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。
许多规划问题用动态规划的方法来处理,常比线性规划或非线性规划更有效。
特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。
动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。
本教材主要介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用。
6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述有这样一类活动过程,其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策,以使整个过程达到最佳的活动效果。
任何一个阶段(stage ，即决策点)都是由输入(input ）、决策（decision ）、状态转移律（transformation function )和输出(output )构成的，如图6-1（a ）所示.其中输入和输出也称为状态(state ）,输入称为输入状态，输出称为输出状态。
树型动态规划补充二叉树的遍历的相关知识：在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。
这就是二叉树的遍历问题。
所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。
“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。
遍历一般按照从左到右的顺序，共有3 种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。
先序遍历的操作定义如下：若二叉树为空，则空操作，否则①访问根结点②先序遍历左子树③先序遍历右子树先序遍历右图结果为：124753689中序遍历的操作定义如下：若二叉树为空，则空操作，否则①中序遍历左子树②访问根结点③中序遍历右子树中序遍历右图结果为：742513869后序遍历的操作定义如下：若二叉树为空，则空操作，否则①后序遍历左子树②后序遍历右子树③访问根结点后序遍历右图结果为：745289631满二叉树：一棵深度为h且有 2^h-1个结点的二叉树。
满二叉树一定为完全二叉树，但是完全二叉树不一定为满二叉树。
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
满二叉树有如下性质：如果一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h;1、它的叶子数是：2^(h-1)2、第k层的结点数是：2^(k-1)3、总结点数是：2^k-1 (2的k次方减一)4、总节点数一定是奇数。
若设二叉树的深度为h，除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。
1、二叉树的序遍历题目描述Description求一棵二叉树的前序遍历，中序遍历和后序遍历输入描述Input Description第一行一个整数n，表示这棵树的节点个数。
接下来n行每行2个整数L和R。
树形动态规划动态规划： 问题可以分解成若⼲相互联系的阶段，在每⼀个阶段都要做出决策，全部过程的决策是⼀个决策序列。
要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。
动态规划就是解决多阶段决策最优化问题的⼀种思想⽅法。
阶段： 将所给问题的过程，按时间或空间（树归中是空间，即层数）特征分解成若⼲相互联系的阶段，以便按次序去求每阶段的解。
状态： 各阶段开始时的客观条件叫做状态。
决策： 当各段的状态取定以后，就可以做出不同的决定，从⽽确定下⼀阶段的状态，这种决定称为决策。
（即孩⼦节点和⽗亲节点的关系）策略： 由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。
状态转移⽅程： 前⼀阶段的终点就是后⼀阶段的起点，前⼀阶段的决策选择导出了后⼀阶段的状态，这种关系描述了由k阶段到k+1阶段（在树中是孩⼦节点和⽗亲节点）状态的演变规律，称为状态转移⽅程。
⽬标函数与最优化概念： ⽬标函数是衡量多阶段决策过程优劣的准则。
最优化概念是在⼀定条件下找到⼀个途径，经过按题⽬具体性质所确定的运算以后，使全过程的总效益达到最优。
树的特点与性质：1、有n个点，n-1条边的⽆向图，任意两顶点间可达2、⽆向图中任意两个点间有且只有⼀条路3、⼀个点⾄多有⼀个前趋，但可以有多个后继4、⽆向图中没有环；拿到⼀道树规题，我们有以下3个步骤需要执⾏：1. 判断是否是⼀道树规题：即判断数据结构是否是⼀棵树，然后是否符合动态规划的要求。
如果是，那么执⾏以下步骤，如果不是，那么换台。
2. 建树：通过数据量和题⽬要求，选择合适的树的存储⽅式。
如果节点数⼩于5000，那么我们可以⽤邻接矩阵存储，如果更⼤可以⽤邻接表来存储(注意边要开到2*n，因为是双向的。
这是⾎与泪的教训)。
如果是⼆叉树或者是需要多叉转⼆叉，那么我们可以⽤两个⼀维数组brother[]，child[]来存储（这⼀点下⾯会仔细数的）。
3. 写出树规⽅程：通过观察孩⼦和⽗亲之间的关系建⽴⽅程。
山东师大附中陈键飞前言自古以来就是NOIP的重要考察内容，在联赛中占的分量大。
对选手能力有一定要求，需要能够熟练地建立动态规划模型。
需要大量做题，初学者不易掌握其思想。
目录基础：基本概念背包问题——一类典型应用 进阶：更多的问题树形DP状态压缩优化：减少状态数目减少状态转移（决策）时间基本概念最长上升子序列状态：f[i]能完全地表示出问题某个或某些本质相同的形态决策：f[i]=min(f[j]+1)状态由哪个状态转移得到阶段：每个i前面的阶段决定后面的阶段，后面的阶段由前面的状态转移得到基本概念石子合并状态f[i,j]决策f[i,j]=min(f[i,k]+f[k+1,j])+w[i,j] 阶段j-i （区间大小）基本概念无后效性后面阶段的状态只受前面阶段的状态的影响 对于任意两个状态，只能单向的进行转移基本概念拓扑图（有向无环图）无后效性f[i]=min(f[j])+1基本概念 非拓扑图（可能有环） 有后效性a →b →c ？b →c →a ？a bc 51111基本概念最优子问题问题最优，只需子问题最优，与到达子问题的路径无关3 5 24 6f(5)最优，只需f(4)最优，与f(4)是怎么到达的无关与路线具体是3 4 6还是2 4 6无关基本概念最优子问题输出1~n中∑(A(i,p[i]))最大的排列f(i)表示用1~n组成的长度为i的序列？ 与到达子问题的路径有关！1 4 3 →6 ？4 2 3 →6 ？基本概念无后效性、最优子问题是否能满足与状态的表示，状态的转移，阶段的划分有关背包问题——一类典型应用 给定n个货币，面值各不相同，问能否凑出m元钱f[i,j]表示前i个货币能否凑出j元f[i,j] = f[i-1,j] （不选j）or f[i-1,j-w[i]]（选j）背包问题——一类典型应用 给定n种货币，每种无限多个，面值各不相同，问能否凑出m元钱f[i,j]表示前i种货币能否凑出j元f[i,j]=f[i-1,j] or f[i,j-w[i]]背包问题——一类典型应用 给定n种货币，第i种有A i个，面值W i，问能否凑出m 元钱将每种货币i拆成A i个价值为W i的货币O(m∑A i)将每种货币i拆成价值为W i,2W i,4W i,8W i……的货币O(m∑log A i)单调队列O(mn) ，暂时跳过背包问题——一类典型应用 给定n种货币分为k组，每组只能选一个，问能否凑出m元f[i,j,k]表示用前1~i-1组和第i组的前j个能否凑出k元。
初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓扑排序(poj1094)(5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串(poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书page149):1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化(poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)以及补充Dp状态设计与方程总结1.不完全状态记录<1>青蛙过河问题<2>利用区间dp2.背包类问题<1> 0-1背包，经典问题<2>无限背包，经典问题<3>判定性背包问题<4>带附属关系的背包问题<5> + -1背包问题<6>双背包求最优值<7>构造三角形问题<8>带上下界限制的背包问题(012背包)3.线性的动态规划问题<1>积木游戏问题<2>决斗（判定性问题）<3>圆的最大多边形问题<4>统计单词个数问题<5>棋盘分割<6>日程安排问题<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)<8>方块消除游戏(某区间可以连续消去求最大效益)<9>资源分配问题<10>数字三角形问题<11>漂亮的打印<12>邮局问题与构造答案<13>最高积木问题<14>两段连续和最大<15>2次幂和问题<16>N个数的最大M段子段和<17>交叉最大数问题4.判定性问题的dp(如判定整除、判定可达性等)<1>模K问题的dp<2>特殊的模K问题，求最大(最小)模K的数<3>变换数问题5.单调性优化的动态规划<1>1-SUM问题<2>2-SUM问题<3>序列划分问题(单调队列优化)6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)<1>凸多边形的三角剖分问题<2>乘积最大问题<3>多边形游戏(多边形边上是操作符,顶点有权值)<4>石子合并(N^3/N^2/NLogN各种优化)7.贪心的动态规划<1>最优装载问题<2>部分背包问题<3>乘船问题<4>贪心策略<5>双机调度问题Johnson算法8.状态dp<1>牛仔射击问题(博弈类)<2>哈密顿路径的状态dp<3>两支点天平平衡问题<4>一个有向图的最接近二部图9.树型dp<1>完美服务器问题(每个节点有3种状态)<2>小胖守皇宫问题<3>网络收费问题<4>树中漫游问题<5>树上的博弈<6>树的最大独立集问题<7>树的最大平衡值问题<8>构造树的最小环。
树型动态规划树型动态规划⼀、基本概念树型动态规划，顾名思义，就是在“树”的数据结构上做动态规划，通过有限次地遍历树，记录相关信息，以求解问题。
通常，动态规划都是线性的或者建⽴在图上的，分为逆推和顺推。
①叶->根，即根的⼦节点传递有⽤的消息给根，之后由根得出最优解的过程。
这种⽅式DP的题⽬应⽤⽐较多。
②根->叶，即需要取所有点作为⼀次根节点进⾏求值，此时⽗节点得到了整棵树的信息，只需要去除这个⼉⼦的DP值的影响，然后再转移给这个⼉⼦，这样就能达到根->叶的顺序动态规划的顺序：⼀般按照后序遍历的顺序，⼏处理完⼉⼦再处理当前结点，才符合树的⼦结构的性质。
实现⽅式：树型DP是通过记忆化搜索实现的，因此采⽤的是递归⽅式，时间复杂度：树型动态规划的时间复杂度基本上是O（n)；若有附加维m，则是O（n * m)⼆、经典问题1.树的重⼼对于⼀颗n个节点的⽆根树，找到⼀个点，使得把树变成以该点为根的有根树时，最⼤⼦树的节点最⼩，换句话说，删除这个点后最⼤连通块的节点数最⼩，那么这个点就是树的重⼼。
解法：任选⼀个节点作为根进⾏dfs然后根据定义动态规划寻找树的重⼼。
2.树的最长路径（最远点对）给定⼀颗n个结点的边带权树找到⼀条最长的路径，换句话说，要找到两个点，使得他们的距离最远，他们之间的路径就是树的最长路径解法：⽤d1[i],d2[i]记录以i为根的⼦树中到叶节点的最⼤值和次⼤值，j是i的⼉⼦①d1[j] + dis[i][j] > d1[i] 则d2[i] = d1[i],d1[i] = d1[j] + dis[i][j]②d1[j] + dis[i][j] > d2[i] 则d2[i] = d1[j] + dis[i][j]3.树的中⼼问题给出⼀颗带权的树，求树中的点，使得此点到树中的其他节点的最远距离最近分析：从任意⼀个点i出发的最长路径的可能形态有两种。
①从i点出发向上，即终点不在以i为根的⼦树中的最长路径长度为u[i]②从i点出发向下，即终点在以i为根的⼦树中的最长路径长度为d1[i]注意：第⼀种⾥⾯不要重复经过i点分别⽤c1[i]和c2[i]记录d1[i]和d2[i]是从哪个⼦树更新来的。
信息学奥赛——树型动态规划的实例分析树型动态规划（Tree Dynamic Programming）是信息学奥赛中常用的一种算法思想，在解决一些与树相关的问题时非常有效。
本文将通过一个具体的实例对树型动态规划进行详细分析。
假设有一棵有根树，每个节点上都有一个非负整数权值，并且每个节点下都可能有若干个子节点。
现在要求选择一些节点，使得选中的节点的权值之和尽可能大，但是不能选择相邻的节点。
我们需要设计一个算法来解决这个问题。
首先，我们可以观察到如果一个节点被选中，那么它的子节点就不能被选中。
于是，我们可以定义一个动态规划的状态dp[i]表示以节点i为根的子树中选择节点的最大权值之和。
对于根节点，我们有两种情况：1. 根节点i被选择，那么它的子节点就不能被选择。
所以dp[i] = sum(dp[j])，其中j表示i的所有子节点。
2. 根节点i不被选择，那么它的所有子节点都可以被选择。
所以dp[i] = sum(max(dp[j], dp[k]))，其中j和k分别表示i的所有孩子节点的子节点。
通过对根节点的两种状态的分析，我们可以得到一个递推关系：dp[i] = max(sum(dp[j]), sum(max(dp[k], dp[l])))，其中j表示i的所有子节点，k和l分别表示i的所有孩子节点的子节点。
接下来，我们需要设计一个合适的递归算法来计算dp[i]。
我们可以使用深度优先（DFS）的方式来处理每个节点，实现递归的过程。
具体的伪代码如下：```DFS(i):visit[i] = truefor j in i的所有子节点：if visit[j] == false:DFS(j)dp[i] += dp[j]for k in i的所有孩子节点：for l in k的所有子节点：dp[i] += max(dp[k], dp[l])```最后，我们只需要调用DFS函数以根节点为参数，可以得到整棵树的最优解。
1. 资源问题1-----机器分配问题F[I,j]:=max(f[i-1,k]+w[i,j-k])2. 资源问题2------01背包问题F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]);3. 线性动态规划1-----朴素最长非降子序列F:=max{f[j]+1}4. 剖分问题1-----石子合并F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);5. 剖分问题2-----多边形剖分F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a);6. 剖分问题3------乘积最大f[i,j]:=max(f[k,j-1]*mult[k,i]);7. 资源问题3-----系统可靠性(完全背包)F[i,j]:=max{f[i-1,j-c*k]*P[I,x]}8. 贪心的动态规划1-----快餐问题F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2) div p3}9. 贪心的动态规划2-----过河f=min{{f(i-k)} (not stone){f(i-k)}+1} (stone); +贪心压缩状态10. 剖分问题4-----多边形-讨论的动态规划F[i,j]:=max{正正f[I,k]*f[k+1,j];负负g[I,k]*f[k+1,j];正负g[I,k]*f[k+1,j];负正f[I,k]*g[k+1,j];} g为min11. 树型动态规划1-----加分二叉树(从两侧到根结点模型)F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}12. 树型动态规划2-----选课(多叉树转二叉树,自顶向下模型)F[I,j]表示以i为根节点选j门功课得到的最大学分f[i,j]:=max{f[t.l,k]+f[t.r,j-k-1]+c}13. 计数问题1-----砝码称重f[f[0]+1]=f[j]+k*w[j];(1<=i<=n; 1<=j<=f[0]; 1<=k<=a;)14. 递推天地1------核电站问题f[-1]:=1; f[0]:=1;f:=2*f[i-1]-f[i-1-m]15. 递推天地2------数的划分f[i,j]:=f[i-j,j]+f[i-1,j-1];16. 最大子矩阵1-----一最大01子矩阵f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;ans:=maxvalue(f);17. 判定性问题1-----能否被4整除g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)18. 判定性问题2-----能否被k整除f[I,j±n mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n20. 线型动态规划2-----方块消除游戏f[i,i-1,0]:=0f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),f[i,p,k+len[j]]+f[p+1,j-1,0]}ans:=f[1,m,0]21. 线型动态规划3-----最长公共子串，LCS问题f[i,j]={0(i=0)&(j=0);f[i-1,j-1]+1 (i>0,j>0,x=y[j]);max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x<>y[j]);22. 最大子矩阵2-----最大带权01子矩阵O(n^2*m)枚举行的起始，压缩进数列，求最大字段和，遇0则清零23. 资源问题4-----装箱问题(判定性01背包)f[j]:=(f[j] or f[j-v]);24. 数字三角形1-----朴素の数字三角形f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);25. 数字三角形2-----晴天小猪历险记之Hill同一阶段上暴力动态规划if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]26. 双向动态规划1数字三角形3-----小胖办证f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])27. 数字三角形4-----过河卒//边界初始化f[i,j]:=f[i-1,j]+f[i,j-1];28. 数字三角形5-----朴素的打砖块f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);29. 数字三角形6-----优化的打砖块f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}30. 线性动态规划3-----打鼹鼠’f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j])31. 树形动态规划3-----贪吃的九头龙32. 状态压缩动态规划1-----炮兵阵地Max(f[Q*(r+1)+k],g[j]+num[k])If (map and plan[k]=0) and((plan[P] or plan[q]) and plan[k]=0)33. 递推天地3-----情书抄写员f:=f[i-1]+k*f[i-2]34. 递推天地4-----错位排列f:=(i-1)(f[i-2]+f[i-1]);f[n]:=n*f[n-1]+(-1)^(n-2);35. 递推天地5-----直线分平面最大区域数f[n]:=f[n-1]+n:=n*(n+1) div 2 + 1;36. 递推天地6-----折线分平面最大区域数f[n]:=(n-1)(2*n-1)+2*n;37. 递推天地7-----封闭曲线分平面最大区域数f[n]:=f[n-1]+2*(n-1):=sqr(n)-n+2;38 递推天地8-----凸多边形分三角形方法数f[n]:=C(2*n-2,n-1) div n;对于k边形f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)39 递推天地9-----Catalan数列一般形式1,1,2,5,14,42,132f[n]:=C(2k,k) div (k+1);40 递推天地10-----彩灯布置排列组合中的环形染色问题f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);41 线性动态规划4-----找数线性扫描sum:=f+g[j];(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)42 线性动态规划5-----隐形的翅膀min:=min{abs(w/w[j]-gold)};if w/w[j]<gold then inc(i) else inc(j);43 剖分问题5-----最大奖励f:=max(f,f[j]+(sum[j]-sum)*i-t44 最短路1-----Floydf[i,j]:=max(f[i,j],f[i,k]+f[k,j]);ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];45 剖分问题6-----小H的小屋F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);46 计数问题2-----陨石的秘密（排列组合中的计数问题）Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);47 线性动态规划------合唱队形两次F:=max{f[j]+1}＋枚举中央结点48 资源问题------明明的预算方案：加花的动态规划f[i,j]:=max(f[i,j],f[l,j-v-v[fb]-v[fa]]+v*p+v[fb]*p[fb]+v[fa]*p[fa]);49 资源问题-----化工场装箱员50 树形动态规划-----聚会的快乐f[i,2]:=max(f[i,0],f[i,1]);f[i,1]:=sigma(f[t^.son,0]);f[i,0]:=sigma(f[t^.son,3]);51 树形动态规划-----皇宫看守f[i,2]:=max(f[i,0],f[i,1]);f[i,1]:=sigma(f[t^.son,0]);f[i,0]:=sigma(f[t^.son,3]);52 递推天地-----盒子与球f[i,1]:=1;f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);53 双重动态规划-----有限的基因序列f:=min{f[j]+1}g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j])54 最大子矩阵问题-----居住空间f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),min(f[i,j,k-1],f[i-1,j-1,k])),min(min(f[i-1,j,k-1],f[i,j-1,k-1]),f[i-1,j-1,k-1]))+1;55 线性动态规划------日程安排f:=max{f[j]}+P[I]; (e[j]<s)56 递推天地------组合数C[I,j]:=C[i-1,j]+C[I-1,j-1]C[I,0]:=157 树形动态规划-----有向树k中值问题F[I,r,k]:=max{max{f[l,I,j]+f[r,I,k-j-1]},f[f[l,r,j]+f[r,r,k-j]+w[I,r]]}58 树形动态规划-----CTSC 2001选课F[I,j]:=w(if i∈P)+f[l,k]+f[r,m-k](0≤k≤m)(if l<>0)59 线性动态规划-----多重历史f[i,j]:=sigma{f[i-k,j-1]}(if checked)60 背包问题(+-1背包问题+回溯)-----CEOI1998 Substractf[i,j]:=f[i-1,j-a] or f[i-1,j+a]61 线性动态规划(字符串)-----NOI 2000 古城之谜f[i,1,1]:=min{f[i+length(s),2,1],f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+w ords[s]}62 线性动态规划-----最少单词个数f[i,j]:=max{f[I,j],f[u-1,j-1]+l}63 线型动态规划-----APIO2007 数据备份状态压缩＋剪掉每个阶段j前j*2个状态和j*2+200后的状态贪心动态规划f:=min(g[i-2]+s,f[i-1]);64 树形动态规划-----APIO2007 风铃f:=f[l]+f[r]+{1 (if c[l]<c[r])}g:=1(d[l]<>d[r]) 0(d[l]=d[r])g[l]=g[r]=1 then Halt;65 地图动态规划-----NOI 2005 adv19910F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];66 地图动态规划-----优化的NOI 2005 adv19910F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;67 目标动态规划-----CEOI98 subtraF[I,j]:=f[I-1,j+a] or f[i-1,j-a]68 目标动态规划----- Vijos 1037搭建双塔问题F[value,delta]:=g[value+a,delta+a] or g[value,delta-a]69 树形动态规划-----有线电视网f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])leaves>=p>=l, 1<=q<=p;70 地图动态规划-----vijos某题F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);71 最大子矩阵问题-----最大字段和问题f:=max(f[i-1]+b,b); f[1]:=b[1]72 最大子矩阵问题-----最大子立方体问题枚举一组边i的起始，压缩进矩阵B[I,j]+=a[x,I,j]枚举另外一组边的其实，做最大子矩阵73 括号序列-----线型动态规划f[I,j]:=min(f[I,j],f[i+1,j-1](ss[j]=”()”or(”[]”)),f[I+1,j+1]+1 (s[j]=”(”or”[” ] , f[I,j-1]+1(s[j]=”)”or”]” )74 棋盘切割-----线型动态规划f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]min{}}75 概率动态规划-----聪聪和可可(NOI2005)x:=p[p[i,j],j]f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1f[I,i]=0f[x,j]=176 概率动态规划-----血缘关系F[A, B]=(f[A0, B]+P[A1, B])/2f[I,i]=1f[I,j]=0(I,j无相同基因)77 线性动态规划-----决斗F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j78 线性动态规划-----舞蹈家F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])79 线性动态规划-----积木游戏F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’])80 树形动态规划（双次记录）-----NOI2003 逃学的小孩朴素的话枚举节点i和离其最远的两个节点j,k O(n^2)每个节点记录最大的两个值，并记录这最大值分别是从哪个相邻节点传过来的。
动态规划专题（六）：树型动态规划（重庆巴蜀中学黄新军）信息学竞赛中通常会出现这样的问题：给一棵树，要求以最少的代价（或取得最大收益）完成给定的操作。
有很多问题都是在树和最优性的基础上进行了扩充和加强，从而变成了棘手的问题。
这类问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优解，因此要用动态规划解决。
和一般动态规划问题一样，这类问题的解决要考虑如下三步：1、确立状态：几乎所以的问题都要保存以某结点为根的子树的情况，但是要根据具体问题考虑是否要加维，加几维，如何加维。
2、状态转移：状态转移的变化比较多，要根据具体问题具体分析，这也是本文例题分析的重点。
3、算法实现：由于模型建立在树上，即为树型动态规划。
【例题1】二叉苹果树【问题描述】有一棵苹果树，如果树枝有分叉，一定是分2叉(就是说没有只有1个儿子的结点)，这棵树共有N个结点(叶子点或者树枝分叉点)，编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。
下面是一颗有4个树枝的树：现在这颗树枝条太多了，需要剪枝。
但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
【文件输入】第1行2个数，N和Q(1<=Q<=N,1<N<=100)。
N表示树的结点数，Q表示要保留的树枝数量。
接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。
第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
【文件输出】输出文件仅一个数，表示最多能留住的苹果的数量。
【样例输入】5 21 3 11 4 102 3 203 5 20【样例输出】21【思路点拨】由题意可知，需要保留的树枝数量为Q条，即保留结点t=Q+1个。
树根必须保留，可以分三种情况讨论保留苹果的最大数。
①树根的左子树为空，全部保留右子树，右子树中保留t-1个结点；②树根的右子树为空，全部保留左子树，左子树中保留t-1个结点；③树根的两棵子树都为非空，设左子树保留k个结点，则右子树保留t-k-1个结点。
要得到保留树根时的苹果最大数，只需要求上述三个方案中的最大值。
设树根为V，左儿子为ch[v,1],右儿子为ch[v，2]，对于①方案，要取得该方案的最大值，需要取得以ch[v，2]为根，保留t-1个结点的最大值。
这时同样具有上述三种方案。
其他②③情况同理；由此可以看出，该问题具有明显的最优子结构性质，每个问题都与左右儿子结点有关系，但不与孙子结点发生关系，具备无后效性；且计算方案时，搜索子结构时具备重叠性，所以可以用动态规划来解决。
阶段和状态：f[v，t]：表示以v为根的树上保留t个节点的最大权值和。
设ch[v，1],ch[v，2]分别存v节点的左右孩子。
状态转移方程：f[v,t]=max{f[ch[v,1]][i]+f[ch[v,2]][t-i-1]+num[v]}(0<=i<=t-1)初始化：f[v,t]=0,(t=0)；f[v,t]=num[v]；(ch[v,1]=0且ch[v,2]=0)Answer=f[1,t]；【例题2】加分二叉树（NOIP2003）【问题描述】设一棵n个结点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为结点编号。
每个结点都有一个分数（均为正整数），记第i个结点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶结点本身的分数。
不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
要求输出；（1）tree的最高加分（2）tree的前序遍历【输入格式】第1行：一个整数n（n<30），为结点个数。
第2行：n个用空格隔开的整数，为每个结点的分数（分数<100）。
【输出格式】第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
【输入样例】55 7 1 2 10【输出样例】1453 1 24 5【思路点拨】本题已经说明了问题的模型是一棵树，而且是一棵中序遍历为1,2,3,…,n的二叉树。
而对于一棵中序遍历为1,2,3,…,n的二叉树有很多种形式，对于样例，下图就列出了3种形式，而按题意，第三种形式得到的得分最大。
性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！因此，假设二叉树的根结点为k，那么中序遍历为1,2,…,n的遍历序列，左孩子序列为1,2,…,k-1，右孩子序列为k+1,k+2,…,n，如下图：我们思考的方式变为，要使得整棵树最优，必须左孩子和右孩子都最优，因此设f[i][j]表示以结点i,i+1,i+2…,j组成的二叉树所得的最大加分；设根为k，则枚举根结点。
d[k]表示k结点的最大分值；故有：f[i,j]=max{f[i,k-1]*f[k+1,j] +d[k]};（1<=i<=k<=j<=n）初始条件：f[i,i]=d[k]Answer=f[1,n]时间复杂度：O(n3)题目还要求输出最大加分树的前序遍历序列，因此要构造这个树，我们只需记录每次的决策值，令p[i,j]=k，表示中序遍历为i,i+1,…,j的二叉树的取最优决策时的根结点为k，最后前序遍历这个树即可。
【例题3】选课（CTSC1997）【问题描述】大学里实行学分。
每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。
学生最后的学分是他选修的各门课的学分的总和。
每个学生都要选择规定数量的课程。
其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。
例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。
我们称《高级语言程序设计》是《数据结构》的先修课。
每门课的直接先修课最多只有一门。
两门课也可能存在相同的先修课。
为便于表述每。
下面举例说明：上例中1是2的先修课，即如果要选修2，则1必定已被选过。
同样，如果要选修3，那么1和2都一定已被选修过。
学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。
每个学生可选课程的总数是给定的。
现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。
假定课程之间不存在时间上的冲突。
【文件输入】输入文件的第一行包括两个正整数M，N(中间用一个空格隔开)，其中M表示待选课程总数(1<=M<=1000)，N表示学生可以选的课程总数(1<=N<=M)。
接下来M行，每行代表一门课，课号依次为1,2,…,M。
每行有两个数(用一个空格隔开)，第一个数为这门课的先修课的课号(若不存在先修课则该项为0)，第二个数为这门课的学分。
学分不超过20的正整数。
【文件输出】输出文件只有一行为一个数，即实际所选课程的学分总数。
【样例输入】7 42 20 10 42 17 17 62 2【样例输出】13【思路点拨】本题与二叉苹果树的显著区别为输入数据是森林或一颗普通有序树，相对于二叉树来说，更复杂些。
对于此情况，可以把森林或普通有序树转换成二叉树，再进行DP设计。
下面分两个步骤来分析此问题：（1）转换树。
输入数据为一棵普通有序树或者森林，根据树的转换规则，把右子树转换成左子树的右儿子，或者右边的一棵树转换成左边树根的儿子。
cin>>n>>m;for(i=1;i<=n;i++){ cin>>k>>v;a[i].value=v;if(son[k]==0)a[k].left=i;else a[son[k]].right=i;son[k]=i;}（2）树上的动态规划创建。
以结点i为阶段，以选的课程数j为状态，以到达叶子结点为边界，以每个结点能取得的最高得分为决策，在整棵树上的决策构成一个决策序列。
用f[i][j]表示结点i为根的子树中取j门课程的最高得分，对树型结构分2种情况进行动态规划设计。
①由于是普通有序树或森林转换成的二叉树，所以需要对右子树进行特殊处理。
当只有右子树时，此时i结点不能选，只能选择i结点的右子树，即选择课程数为j。
所以此时的状态转移方程为：f[i][j]=f[i.r,j]。
②由于要选择左子树时，树根必须选择，所以可以把只有左子树和左右子树都有两种合并起来进行考虑，得到动态规划方程为：f[i][j]=max{f[i.l][k]+f[i.r][j-k-1]+a[i]}(0<=k<=j-1) 最后取①②两种情况中的最大值，即可得到在i结点处取j门课程的最大值。
时间复杂度：O(n2m)【例题4】数字转换【问题描述】如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y>x且y的约数和为x，那么x也可以变成y。
例如，4可以变为3，1可以变为7。
限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。
【文件输入】输入一个正整数n【文件输出】输出不断进行数字变换且没有重复数字出现的最多变换步数。
【样例输入】7【样例输出】3【样例说明】一种方案为：4→3→1→7。
【数据范围】n<=50 000。
【思路点拨】先预处理出每个数的约数，然后很明显就是求树的最长链问题。
一棵有根树的最长链，可能出现如下图的两种情况：对于每个结点我们都要记录两个值：d1[i]表示以i为根的子树中，i到叶子节点的距离最大值；d2[i]表示以i为根的子树中，i到叶子节点的距离次大值；令j是i的儿子。
则：①若d1[j]+1>d1[i]，则d2[i]=d1[i]; d1[i]=d1[j]+1;②否则，若d1[j]+1>d2[i]，则d2[i]=d1[j]+1;最后扫描所有的结点，找最大的d1[i]+d2[i]的值。
【例题5】战略游戏【问题描述】Bob喜欢玩电脑游戏，特别是战略游戏。
但是他经常无法找到快速玩过游戏的办法。
现在他有个问题。
他要建立一个古城堡，城堡中的路形成一棵树。
他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。
注意：某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。
请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。
【文件输入】输入文件中数据表示一棵树，描述如下：第一行N，表示树中结点的数目。
