※动态规划经典教程

《※动态规划经典教程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划经典教程Directory1．1下降/非降子序列问题：例题1拦截导弹例题二合唱队形※例题3BuyLowBuyLower例题4船1.2背包问题例题5装箱问题例题6砝码称重※例题7积木城堡例题8采药例题9开心的金明Unac例题10金明的预算方案例题11MoneySystems例题12新年趣事之打牌1.3其它问题例题13挖地雷问题2.1数塔问题例题14数塔问题例题15Henry捡钱2.2街道问题例题16街道问题2.3最长公共子序列问题例题17最长公共子序列例题18回文词※例题19调整队形2.4背包问题的拓展例题2

2、0找啊找啊找GF※例题21多多看DVD（加强版）2.5石子合并问题（区间DP）例题22石子合并例题23能量项链例题24统计单词个数2.6其他问题例题25花店橱窗设计例题26Divisibility3.1矩阵问题例题27盖房子3.2多进程动态规划例题28方格取数4.树型动态规划例题29加分二叉树例题30ABinaryAppleTree苹果二叉树例题31选课第一节动态规划基本概念一，动态规划三要素：阶段，状态，决策。他们的概念到处都是，我就不多说了，我只说说我对他们的理解：如果把动态规划的求解过程看成一个工厂的生产线，

3、阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。下面举个例子：要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成

4、固态=_=

5、

6、）。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。经过这个例子相信大家对动态规划有所了解了吧。下面在说说我对动态规划的另外一个理解：用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同

7、一阶段。这样对图求最优路径就是动态规划问题的求解。二，动态规划的适用范围动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：最优子结构（最优化原理）无后效性最优化原理在下面的最短路径问题中有详细的解答；什么是无后效性呢？就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。而求状态N时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规划中形成的图无环

8、的原因。也就是说当前状态是前面状态的完美总结，现在与过去无关。。。当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。三，动态规划解决问题的一般思路。拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：（1）模型匹配法：最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时

9、要小心条件，三思而后行。这些基本模型在先面的分类中将一一介绍。（2）三要素法仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同：先确定阶段的问题：数塔问题，和走路问题（详见解题报告）先确定状态的问题：大多数都是先确定状态的。先确定决策的问题：背包问题。（详见解题报告）一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。（3）寻找规律法：这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。（4）边界条件法找到问题的边界条件，然后考虑边界条件与它

10、的领接状态之间的关系。这个方法也很起效。（5）放宽约束和增加约束这个思想是在陈启锋的论文里看到的，具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。第二节动态规划分类讨论这里用状态维数对动态规划进行了分类：1.状态是一维的1．1下降/非降子序列问题：问题描述： {挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解}在一个无序的序列a1,a2,a