动态规划 分类动态规划 分类.docVIP

动态规划分类 1、背包模型 ??? 包括0-1背包、无限背包、有限背包、有价值背包、小数背包（贪心即可)等，是极为经典的模型，其转化与优化也是很重要的。 H P4^ k v3T V A2、最长非降子序列模型 7i _ F+E N H g O8| | | s???? 改版：渡河问题、合唱队型等 3、最大子段和模型 改版：K大子段和、最佳游览，最大子矩阵和等。 4、LCS模型 ?:p0n E m$v |+r???? 改版：回文字串、多串的LCS等 5、括号序列模型 M Y3e V D:D???? 改版：关灯问题（TSOJ）、charexp（TSOJ）、最大算式等，核心思想在于以串的长度为阶段。 6、递推模型 p:l s#U i _1J L }???? 这类题是属于徘徊在DP与递归之间得一类题，本质是类似于记忆化有哪些信誉好的足球投注网站的一种填表，有很强的数学味。 e n o A:l V7、线段覆盖问题 ???? 改版：Tom的烦恼（TOJ）等。经常利用到离散化等技巧辅助。 ^g R V1e+hF8、单词划分模型 ???? 和LCS基本上构成了字符串DP的主要类型。改版：奇怪的门（TOJ）等。 9、股票模型 8u F.[ xm |8g!{????? 这是DP优化的经典模型。改版有换外汇等。 ,o/z yw ?5\/d10、连续段划分模型 ??? 即要求把数列划分成k个连续段，使每段和的最大值最小。改版有任务调度等。 x0e B6d k X j8tv1| Y11、游戏模型 ???? 这类题的阶段（一般是时间）和决策（一般就是游戏目标）很清楚，因此比较容易想到。改版：免费馅饼（NOI98）、Help Jimmy（CEOI2000）、瑰丽华尔兹（NOI2005，优化需要多费功夫）。dp注意的一些总结/sgr123/blog 好好看看 看完，做完，想完，总结完后： 22/oblog3/user1/40/subject/index.html 1.dp一定要边界条件。关于初始值的问题，这是dp的起点，是dp中除方程外最终要的东西，dp过程中的每一个值必须都符合他的状态所表示的意义，否则就是错的，以前方程写对了，但是在这个问题上却经常出错，看了dd_engi大牛的《背包问题九讲》中关于背包恰好放满，与可不放满的最大值大求法的比较后才恍然大悟，除非所有的初始边界在此状态定义下他的有意义的值就是0，否则必须初始化。例如背包。（初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。——《背包问题九讲》） 2.初始最小值不要想当然的赋0，有时候要求的值可能是负的，一定要看清题意，注意赋-∞，但是再用计算机表示的时候不要赋的过大，或过小，因为中间的运算过程中可能会中间值越界产生215错误而爆掉 3.递推顺序每一步怎样取最大值，以及每一步的值对后来有什么影响都要考虑全~~再开始编，不要一出来方程就动手 4.先考虑清楚，必须一次ac！ 5.始终遵循dp每一步都只用已经算出来的！！拿到一个题一定要 先想好 数据结构（在纸上写好），算 法框架（最好也在纸上写好）胸有成竹再下笔！！！否则则只是浪费时间！！！ 6.不要想当然的把所有的最优化的题目都认为是dp，往往贪心和模拟能够发挥巨大作用！！不是dp的题用dp去做，绝对是错误的！！ 7.不是动归方程写出来就万事大吉了，必须能证明它的无后效性，必须满足最有子结构，过于复杂的方程往往是错误的，即使分类考虑的情况很多，但是每一类也应该很简洁，必须证明它的正确性再动手，否则是在白费力气。 8.一定要考虑全面，动归方程一定要包含所有的情况。 9.再说一遍！实现的时候一定要注意递推边界和循环范围，每一步用到的值都是已经求出来的，初始化！一、?多阶段决策过程的最优化问题 问题的提出首先，例举一个典型的且很直观的多阶段决策问题:[例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A-E。求A-E的最省费用。 如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择，一是走到B1，一是走到B2，一是走到B3。若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是