动态规划经典课程介绍：做了一些题目之后对DP有了一些想法，所以写了这个总结：第一节动态规划的基本概念，动态规划的三个要素：阶段、状态、决策。他们的概念无处不在，我就不多说了。我只想说一下我对它们的理解：如果把动态规划的求解过程看成是一个工厂的一条生产线，阶段是生产某种商品的不同环节，状态是工件的当前形态，决策是工件的操作。很明显，不同的阶段是产品之前状态的总结，小的结构成为最终的整条生产线。每个状态都是相关的(下一个状态是由前一个状态做出某个决定后生成的)。这里举个例子：生产一批冰淇淋，这个过程有很多环节：买牛奶，净化牛奶，放入工厂加工，加工好的商品包装，包装后销售.这样每个环节都可以看作一个阶段；产品在不同的时间有不同的状态。刚开始的时候，他们只是白牛奶。进入生产后，被制成各种形状。从冰箱里拿出来之后，就变成冰淇淋了(从液体变成固体)。每一种形态都是一种状态，通过冷冻的操作从液体变成固体，这是一种决定。一个状态在一个决定之后变成另一个状态。这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。经过这个例子，相信大家对动态规划有所了解。我来说一下对动态规划的另一种理解：用图论来理解动态规划：将动态规划中的状态抽象成一个点，在直接相关的状态之间连接一条有向边，状态转移的代价就是边的权重。这样就形成了有向无环图AOE网络(为什么是无环的？往下看)。对图进行拓扑排序，删除一条边后，0度的状态出现在同一阶段。这样，找到图的最优路径就是动态规划问题的解。二、动态规划的适用范围动态规划是用来解决多阶段决策优化问题的，但不是所有的优化问题都可以用动态规划来解决？一般在题目中出现寻找最优解的问题时要考虑动态规划，但要能使用要满足两个条件：最优子结构(优化原理)没有后效优化原理，下面的最短路径问题有详细的解答；什么是无后遗症？也就是说，解状态I的时候用状态j，解状态k…状态N的时候用状态j，而状态I用来解状态N，所以解状态的过程形成了一个循环，所以不能用动态规划求解，这也是为什么用图论的方法，动态规划中形成的图没有循环的原因。也就是说，现在的状态是对以前状态的完美总结，现在与过去无关。当然，如果改变划分状态或阶段的方法，就满足了无后效的要求，这样的问题还是可以通过动态规划来解决的。三、动态规划解决问题的总体思路。得到多阶段决策的优化问题后，第一步是判断这个问题是否可以用动态规划来解决。如果不是，就要考虑搜索或者贪婪。当确定问题可以通过动态规划解决时，应采用以下方法解决：(1)模型匹配法：这种方法是首要考虑的。挖掘问题的本质，如果发现问题是你熟悉的基本模型，直接套用，但要注意一些小的改动。现在，当你申请试题时，你应该小心条件和三思而后行。这些基本模型将在下面的分类中逐一介绍。(2)三要素法认真分析问题，试图确定动态规划的三要素。不同的问题有不同的方向：先确定阶段：塔数，走(详见问题解决报告)。大部分都是先确定状态。首先确定决策的问题：背包问题。(详见问题解决报告。)一般先从明显的地方说起。至于怎么知道哪一个明显是体验问题，多做做问题就知道了。

(3)搜索正则方法：这个方法很简单。耐心的推送了几组数据后，再看他们的规律，总结规律之间的共性，有点贪心。(4)边界条件法求出问题的边界条件，然后考虑边界条件与其主导状态的关系。这个方法也很管用。(5)放松约束和增加约束的思想见于陈奇峰的论文，具体内容是增加一些条件或删除一些条件以使问题明确。第二节讨论了动态规划的分类。这里，动态规划按状态维数分类：1。状态是一维1.1下降/非下降子序列问题：问题描述：{挖掘题目的本质，但是一旦抽象成这样的描述，就可以用这个方法求解}在一个无序的序列a1，a2，a3，a4…an中，发现最长的序列满足：ai

Ajak…am，ijk … m(最长的降序子序列)。问题分析：如果第一个i-1号用的是ak(akai或ak)，

Ai(或aj

Ai){最长降序子序列}求解部分代码：opt[0]:=；{is or-}==0toi-(a [j] a [I])和(opt[j]1 opt[I])[I]:=opt[j]1；ans :=-；for I :=1 ondoifopt[I]ans nans :=opt[I]；{ans是最终解决方案}复杂度：从上面的实现中不难看出时间复杂度为O(N2)，空间复杂度为O(n)；例1拦截导弹(missile.pas/c/cpp)来源：NOIP1999(改进小组)问题1[问题描述]一个国家开发了一种导弹拦截系统来防御敌人的导弹攻击。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹可以达到任何高度，但未来的每一发炮弹都不能高于上一发。一天，雷达发现一枚敌人的导弹飞来。由于该系统还处于试验阶段，所以只有一个系统，所以有可能无法拦截所有导弹。依次输入导弹飞行的高度(雷达给出的高度数据是不大于30000的正整数)，计算这个系统最多能拦截多少导弹，如果要拦截所有导弹，至少要配备多少这样的导弹拦截系统。[输入文件]导弹. in列出了排成一行依次飞行的导弹的高度。[输出文件]导弹.出两行，分别是可以拦截的最大导弹数，以及拦截所有导弹的最小系统数[输入样本]* * * * * * * * * * 5[输出样本]62[提交链接]http://www.rqnoj.cn/Problem_217.html[Q

题分析】有经验的选手不难看出这是一个求最长非升子序列问题，显然标准算法是动态规划。以导弹依次飞来的顺序为阶段，设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。状态转移方程：opt[i]=max(opt[j])+1(h[i]>=h[j]，0=

=a[i])and(opt[j]+1>opt[i])thenopt[i]:=opt[j]+1;anslen:=0;fori:=1tondoifopt[i]>anslenthenanslen:=opt[i];fillchar(opt,sizeof(opt),0);a[0]:=-maxlongint;fori:=1tondoforj:=i-1downto0doif(a[j]

opt[i])thenopt[i]:=opt[j]+1;anstime:=0;fori:=1tondoifopt[i]>anstimethenanstime:=opt[i];end;procedureprint;beginwriteln(anslen);writeln(anstime);close(input);close(output);end;begininit;main;print;end.例题2合唱队形(chorus.pas/c/cpp)来源：NOIP2004(提高组)第一题N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1

Ti+1>…>TK(1

opt1[i])thenopt1[i]:=opt1[j]+1;a[n+1]:=-maxlongint;fori:=ndownto1doforj:=i+1ton+1doif(a[j]

opt2[i])thenopt2[i]:=opt2[j]+1;ans:=0;fori:=1tondoifopt1[i]+opt2[i]>ansthenans:=opt1[i]+opt2[i];end;procedureprint;beginwriteln(n-ans+1);close(input);close(output);end;begininit;main;print;end.例题3BuyLowBuyLower(buylow.pas/c/cpp)来源:USACO4-3-1【问题描述】“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:"逢低吸纳，越低越买"这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。以下面这个表为例，某几天的股价是:天数****1112股价********87这个例子中，聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法):天数25610股价69686462【输入文件】buylow.in第1行:N(1

=a[j]，0=

a[i]，opt[j]=opt[i]-1){sum代表求和}答案=sum(F(j)){0

a[i])and(opt[j]+1>opt[i])thenopt[i]:=opt[j]+1;fori:=1tondobeginj:=i-1;while(j>0)and((opt[i]

opt[j])or(a[i]

a[j]))dodec(j);next[i]:=j;end;F[0,1]:=1;fori:=1ton+1doforj:=i-1downtonext[i]doif(opt[j]=opt[i]-1)and(a[j]>a[i])thenHinc(F[i],F[j]);end;procedureprint;vari,top,m:longint;beginwrite(opt[n+1]-1,'');top:=maxsize;while(top>1)and(F[n+1][top]=0)dodec(top);write(F[n+1,top]);fori:=top-1downto1dobeginm:=F[n+1,i];whilem

D2那么一定会相交，反之则不会相交。当C1>C2时，如果D1

xdodec(j);ifi

j;ifj>Lthenquick(L,j);ifi

opt[i])thenopt[i]:=opt[j]+1;ans:=-maxlongint;fori:=1tondoifans

0)dobegininit;main;read(x,y);end;close(input);close(output);end.1.2背包问题首先说说背包问题的基本模型：现有动态规划最新问题N个物品，每个物品的价值为V，重量为W。求用一个载重量为S的背包装这些物品，使得所装物品的总价值最高。背包问题用贪心和搜索解，当然效果不佳，不过在我的贪心和搜索总结中会说到。显然标准的解法是动态规化，我在解决这个问题时习惯设计一维状态，还可以设计二维的，二维状态在下面会讲，现在只讨论用一维状态实现背包问题。背包问题的分类：(1)小数背包：物品的重量是实数，如油，水等可以取1.67升……(2)整数背包：

0/1背包：每个物品只能选一次，或不选。不能只选一部分

部分背包：所选物品可以是一部分。(3)多重背包：背包不只一个。小数背包：在贪心总结中会细讲。整数背包：部分背包：同小数背包。0/1背包：这个问题是最经常出现的问题，应该熟练掌握。我们先看一下0/1背包的简化版：现有N个物品，每个物品重量为W，这些物品能否使在载重量为S的背包装满（即重量和正好为S）？如果不能那能使物品重量和最重达到多少？针对这一问题我们以物品的个数分阶段，设计一个状态opt[i]表示载重量为i的背包可否装满，显然opt[i]的基类型是boolean。决策是什么呢？当要装第i个物品时，如果前i-1个物品可以使载重为k的背包装满，那么载重为k+w[i]的背包就可以装满。于是对于一个opt[j]来说，只要opt[j-w[i]]是true（表示可装满）那opt[j]就可以装满，但要注意：针对每一个物品枚举背包的载重量时如果这样正向的推导会使同一个物品用好几次，因为k+w[i]可装满那k+w[i]+w[i]就可装满，但实际上是装不满的因为物品只有一个。解决这个问题很简单，只要逆向推导就OK了。这样划分阶段，设计状态，满足无后效性么？显然对于物品只有一个每一个阶段都是独立的，物品的顺序并不影响求解，因为装物品的次序不限。而对于opt[j]只考虑opt[j-w[i]]而不考虑后面的，所以满足无后效性。有了上面的分析不难写出状态转移方程：opt[j]:=opt[j-w[i]]{opt[j-w[i]]=true}时间复杂度：阶段数O(S)*状态数（O(N)）*转移代价（O(1)）=O（SN）下面看几个例题：例题5装箱问题(pack.pas/c/cpp)来源：NOIP2001(普及组)第四题【问题描述】有一个箱子容量为V（正整数，0

0dobegininc(top);a[top]:=m;inc(tothig,m);read(m);end;fori:=1totopdoforj:=tothigdownto1doif(j-a[i]>=0)and(opt[ii,j-a[i]])thenopt[ii,j]:=true;end;ans:=maxhig;whilenotopt[1,ans]dodec(ans);whilenotcan(ans)dodec(ans);writeln(ans);end;begininit;main;end.回顾上面的内容充分说明动态规划的本质就是递推。其实按照我的理解（动规涉及最优决策，递推是单纯的总结）背包问题的简化版更准确点算是递推而非动态规划，至于动归和递推之间的界线本来就很模糊（至少我这么认为）把它看做什么都可以，没必要咬文嚼字。回到0/1背包的原问题上（如果你忘了就去上面看看）。如果在不知道这个模型的情况下我们怎么做这个题呢？这就要用到第一节提到的方法二：三要素法。题目中明确说明对于一个物品要不就拿走要不就放下，其实题目赤裸裸的告诉我们决策就是不拿（用0表示）或拿（用1表示）。这样想都不用想就知道了决策，这也是本题的突破口。知道了决策写个搜索的程序应该是很轻松的了。那么阶段是什么呢？显然，给你一堆东西让你往包里塞，你当然是一个一个的拿来，塞进去。那么阶段很明显就是物品的个数。状态又是什么呢？有的人在装东西时有个习惯（比如说我）就是先把东西分类，然后把同类的东西打个小包，最后再把小包放进去，我们可以按这个思想给物品打一些小包，也就是按照单位为1的递增的顺序准备好多个小包，比如载重是6的包，可以为它准备载重是1，2，3，4，5的小包。这样状态就可以想出来了：设计状态opt[i，j]表示装第i个物品时载重为j的包可以装到的最大价值。opt[i-1,j](j-w[i]

0)状态转移方程：opt[i,j]=max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]}(j-w[i]>=0,i>0)(w[i]:第i个物品的重量，v[i]第i个物品的价值)解释：要载重为j的背包空出w[i]（j-w[i]）的空间且装上第i个物品，比不装获得的价值大就装上它。边界条件：opt[0,i]=0;(i∈{1..S})注：这种二维的状态表示应该在下节讲，但是为了方便理解先在这里说了。上面的方法动态规划三要素都很明显，实现也很简单。但是在我初学背包时却用另外一种一维的状态表示法。用第一节说的思考方法五（放宽约束和增加约束）再重新思考一下这个问题：怎么放宽约束呢？把题目中的价值去掉，不考虑价值即最优就变成背包问题的简化版了。那简化版的求解对我们有何启示呢？再一次增加约束：背包只能装满。显然对于N个装满背包的方案中只要找到一个价值最大的就是问题的解。那么装不满怎么办呢？其实装不满背包，它总要达到一定的重量（X）。我们可以把这种情况看作是装满一个载重为X的小包。总结一下上面的思维过程：放宽约束让我们找到问题的突破口——和背包问题简化版一样，我们可以确定载重为S的背包是否可以装满。增加约束让我们找到问题的求解方法——在装满背包的方案中选择最优的一个方案。这样问题就解决了。设计一个状态opt[j]表示装满载重为j的背包可获得的最大价值。对于第i个物品，只要opt[j-w[i]]可以装满且opt[j-w[i]]+v[i]比opt[j]大就装上这个物品（更新opt[j]）。怎么使opt[j]既有是否构成又有最优的概念呢？opt[j]只表示最优，只不过使初始条件+1，判断opt

动态规划对矩阵算法连乘问题的总结 动态规划的适用范围

什么是动态规划，我们如何描述？

动态编程算法通常基于一个递归公式和一个或多个初始状态。当前子问题的解将从前一个子问题的解推导出来。使用动态规划求解问题只需要多项式时间复杂度，因此比回溯法和暴力法快得多。首先需要找到某个状态的最优解，然后在它的帮助下找到下一个状态的最优解。

“状态”用来描述这个问题的子问题的解。

递归、递归和迭代

迭代算法是计算机解决问题的基本方法。它利用计算机的运算速度快，适合重复运算，使计算机可以重复执行一组指令(或某些步骤)，每次执行指令(或这些步骤)时，从原始值导出变量的新值。

一般来说，迭代俗称“循环”。在编程语言中，for\\\loop等都是循环

递归与循环：理论上所有的递归函数都可以转化为迭代函数，反之亦然，但是代价通常比较高。递归多了，内存占用也会增加。

递归和递归：

从程序的角度来说，递归表明你调用自己，但是递归没有这样的形式。

递归就是从问题的最终目的出发，逐渐把复杂的问题变成简单的问题，最后得到问题。反了。递归从一个简单的问题开始，一步一步发展，最后得到问题。是正面的。

在递归中，问题的n要求在计算前已知，而递归可以在计算中确定，不需要在计算前知道n。

一般来说递归比递归效率高(当然如果递归可以计算的话)。

动态规划和贪婪算法的区别

相同点

动态规划和贪婪算法都是递归算法。有局部最优解来导出全局最优解。

差异

贪婪算法：

在贪婪算法中，每一个贪婪决策都是不可改变的，因为贪婪策略是从上一个最优解推导出下一个最优解，而上一个最优解是不保留的。

从(1)中的介绍可以知道，贪心法的正确条件是每一步的最优解必须包含前一步的最优解。

动态编程算法：

全局最优解必须包含一个局部最优解，但不一定包含以前的局部最优解，所以需要记录所有以前的最优解

动态规划的关键是状态转移方程，即如何从局部最优解推导出全局最优解

边界条件：可以直接得到的最简单的局部最优解

贪心法的基本思路

从问题的某个初始解开始，我们逐渐逼近某个给定的目标，以尽快得到更好的解。当算法到达某一步时，算法停止。该算法存在问题：

不能保证最终的解决方案是最好的。

不能用来求最大值或最小值的解；

只能找到满足一定约束的可行解的范围。实现算法的过程：从问题的一个初始解开始；

能够朝着给定的总体目标更进一步

找到可行解的解元素；

问题的可行解由所有解元素组成。

贪婪算法最经典的例子

，给钱。比如中国的货币只看人民币，包括1元，2元，5元，10元20，50，100

如果我要16块钱，我可以拿16块1，8块2，但是怎么才能拿的最少？如果我用贪婪，我每次拿那个都会得到最大的。比如16，第一次拿不起20，拿10块，OK，然后6块，然后5块，然后1块，就是三个十，五，一。

贪婪是你每次能拿的最大的东西。

但必须注意的是，贪婪并没有得到最优解，也就是说贪婪不一定得到最少的张数，贪婪只能得到更好的解，贪婪算法非常容易得到。再注意一下，为什么我们的钱可以贪？因为我们国家的货币大小是设计好的，可以让贪婪算法计算出最优解(一般一个国家的硬币应该是这样设计的)。如果换个方式设计，情况就不一样了。

例如，公司

想拿6块钱，怎么拿？如果你很贪心，先拿四个，再拿两个，一共三块钱

实际最优呢？两个3块钱就够了。

寻找最优解的问题，从根本上说是对解空间的遍历。最直接的暴力分析很容易得到，最优解的解空间通常呈指数增长，所以暴力耗竭不可行。大多数最优解问题可以分为子问题。如果把解空间的遍历看成是子问题树的遍历，那么以某种形式遍历整棵树一次就可以得到最优解。如上分析，不可行。贪心和动态规划本质上都是修剪子问题树。两个算法要求问题的一个性质是“子问题最优性”。也就是说，构成最优解的每个子问题的解对于这个子问题本身来说肯定是最优的。如果从上到下看问题树(以原问题为根)，每次只需要遍历代表最优解的子树，就可以保证得到全局最优解。说白了，你可以简单的用一个值(最优值)来表示整个子树，而不是找出这个子树可能代表的所有值。动态规划法代表了这类问题的一般解法。我们从下到上(从叶到根)构造子问题的解。对于每一个子树的根，我们找到下面每一片叶子的值，把最好的值作为自己的值，丢弃其他的值。动态规划的成本取决于备选方案的数量(树叉数)和子问题的数量(树节点数，还是树高？)。贪心算法是动态规划方法的特例。贪心在于可以证明每个子树的根的值不依赖于下层叶子的值，只依赖于问题的现状。换句话说，您可以在不知道节点的所有子树的情况下找到该节点

的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。因此用“贪心”来描述这个算法的本质。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代价只取决于子问题的数目，而选择数目总为1。

动态规划：从新手到专家

意识到，DP是由上一个状态解找到下个状态解，所以一般要去找上一个状态，如

标签： #动态规划最新问题