引言：本人在做过一些题目后对dp有些感想，就写了这个总结：
第一节动态规划基本概念。
一，动态规划三要素：阶段，状态，决策。
他们的概念到处都是，我就不多说了，我只说说我对他们的理解：
如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。
下面举个例子：
要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。
一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。
经过这个例子相信大家对动态规划有所了解了吧。
下面在说说我对动态规划的另外一个理解：
用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。这样就形成了一个有向无环图aoe网（为什么无环呢？
往下看）。对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。这样对图求最优路径就是动态规划问题的求解。
二，动态规划的适用范围。
动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？
一般在题目**现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：
最优子结构（最优化原理）
无后效性。最优化原理在下面的最短路径问题中有详细的解答；
什么是无后效性呢？
就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态n。
而求状态n时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规划中形成的图无环的原因。
也就是说当前状态是前面状态的完美总结，现在与过去无关。。。
当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。
三，动态规划解决问题的一般思路。
拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：
1）模型匹配法：
最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时要小心条件，三思而后行。这些基本模型在先面的分类中将一一介绍。
2）三要素法。
仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同：
先确定阶段的问题：数塔问题，和走路问题（详见解题报告）
先确定状态的问题：大多数都是先确定状态的。
先确定决策的问题：背包问题。（详见解题报告）
一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。
3）寻找规律法：
这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。
4）边界条件法。
找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。
5）放宽约束和增加约束。
这个思想是在陈启锋的**里看到的，具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。
第二节动态规划分类讨论。
这里用状态维数对动态规划进行了分类：
1.状态是一维的。
1．1下降/非降子序列问题：
问题描述：
在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：ai<=aj<=ak…<=am,且iaj>ak…>am,且i>j>k…>m.（最长下降子序列）。
问题分析：如果前i-1个数中用到ak (ak>ai或ak<=ai)构成了一个的最长的序列加上第i个数ai就是前i个数中用到i的最长的序列了。那么求用到ak构成的最长的序列有要求前k-1个数中……
从上面的分析可以看出这样划分问题满足最优子结构，那满足无后效性么？显然对于第i个数时只考虑前i-1个数，显然满足无后效性，可以用动态规划解。
分析到这里动态规划的三要素就不难得出了：如果按照序列编号划分阶段，设计一个状态opt[i] 表示前i个数中用到第i个数所构成的最优解。那么决策就是在前i-1个状态中找到最大的opt[j]使得aj>ai(或aj<=ai)，opt[j]+1就是opt[i]的值；用方程表示为：
opt[i]=max(opt[j])+1 (0<=jopt[i]=max(opt[j])+1 (0<=jai)
实现求解的部分**：
opt[0]:=maxsize；
for i:=1 to n do
for j:=0 to i-1 do
if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if opt[i]>ans then ans:=opt[i];
复杂度：从上面的实现不难看出时间复杂度为o（n2），空间复杂度o（n）；,**：noip1999(提高组) 第一题。
问题描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入文件】单独一行列出导弹依次飞来的高度。
输出文件】两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数。输入样例】
输出样例】
问题分析】有经验的选手不难看出这是一个求最长非升子序列问题，显然标准算法是动态规划。
以导弹依次飞来的顺序为阶段，设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。
状态转移方程：
opt[i]=max(opt[j])+1 (h[i]>=h[j],0=最大的opt[i]就是最终的解。
这只解决了第一问，对于第二问最直观的方法就是求完一次opt[i]后把刚才要打的导弹去掉，在求一次opt[i]直到打完所有的导弹，但这样做就错了。
不难举出反例： 6 1 7 3 2
错解： 6 3 2/1/7 正解：6 1/7 3 2
其实认真分析一下题就回发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题。
求最长上升序列和上面说的求最长非升序列是一样的，这里就不多说了。
复杂度：时间复杂度为o（n2），空间复杂度为o（n）。
源**】program missile;
constfin=''
fout=''
maxn=10000;
vara,opt:array[0..maxn] of longint;
n,anslen,anstime:longint;
procedure init;
varx:longint;
beginassign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
n:=0;repeat
inc(n);
read(a[n]);
until seekeof;
end;procedure main;
vari,j:longint;
beginfillchar(opt,sizeof(opt),0);
a[0]:=maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]>=a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
anslen:=0;
for i:=1 to n do
if opt[i]>anslen then
anslen:=opt[i];
fillchar(opt,sizeof(opt),0);
a[0]:=maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt[i]) then
opt[i]:=opt[j]+1;
anstime:=0;
for i:=1 to n do
if opt[i]>anstime then
anstime:=opt[i];
end;procedure print;
beginwriteln(anslen);
writeln(anstime);
close(input);
close(output);
end;begin
init;main;
print;
end., **：noip2004(提高组) 第一题。
n位同学站成一排，**老师要请其中的(n-k)位同学出列，使得剩下的k位同学排成合唱队形。
合唱队形是指这样的一种队形：设k位同学从左到右依次编号为1，2…，k，他们的身高分别为t1，t2，…，tk，则他们的身高满足t1<..ti+1>…>tk(1<=i<=k)。
动态规划作业完整
1 1 设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线？把a看作终点，该问题可分为4个阶段。fk sk 表示从第k阶段点sk到终点a的最短距离。f4 b1 20，f4...
超级画板动态几何教程10问题
10问题汇编。开发设计 超级画板 的理念之一，就是希望老师们淡化技术，少用精力去学技术，多花功夫在创造性的教学设计上。技术问题交给技术人员去解决，老师们把主要精力投入教书育人的创造性劳动。例如，有了椭圆要作出它的焦点，作一个圆的外切正多边形，画一个动态正12面体，这些都是数学上和计算机技术中已经解决...
数学建模8 动态规划和目标规划
一 动态规划。1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的优化问题。但是一些与时间无关的静态规划 如线性规划 非线性规划 只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。2.基本概念 基本方程 1 阶段。2 状态。3 决策。4 策...