A. 动态规划算法程序例子
给你导弹拦截的吧：
[问题描述]
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间至少有一个空格），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
[输入输出样例]
INPUT：
389 207 155 300 299 170 158 65
OUTPUT：
6（最多能拦截的导弹数）
2（要拦截所有导弹最少要配备的系统数）
[问题分析]
我们先解决第一问。一套系统最多能拦多少导弹，跟它最后拦截的导弹高度有很大关系。假设a[i]表示拦截的最后一枚导弹是第i枚时，系统能拦得的最大导弹数。例如，样例中a[5]=3，表示：如果系统拦截的最后一枚导弹是299的话，最多可以拦截第1枚（389）、第4枚（300）、第5枚（299）三枚导弹。显然，a[1]~a[8]中的最大值就是第一问的答案。关键是怎样求得a[1]~a[8]。
假设现在已经求得a[1]~a[7]（注：在动态规划中，这样的假设往往是很必要的），那么怎样求a[8]呢？a[8]要求系统拦截的最后1枚导弹必须是65，也就意味着倒数第2枚被拦截的导弹高度必须不小于65，则符合要求的导弹有389、207、155、300、299、170、158。假如最后第二枚导弹是300，则a[8]=a[4]+1；假如倒数第2枚导弹是299，则a[8]=a[5]+1；类似地，a[8]还可能是a[1]+1、a[2]+1、……。当然，我们现在求得是以65结尾的最多导弹数目，因此a[8]要取所有可能值的最大值，即a[8]=max{a[1]+1,a[2]+1,……，a[7]+1}=max{a[i]}+1 (i=1..7)。
类似地，我们可以假设a[1]~a[6]为已知，来求得a[7]。同样，a[6]、a[5]、a[4]、a[3]、a[2]也是类似求法，而a[1]就是1，即如果系统拦截的最后1枚导弹是389，则只能拦截第1枚。
这样，求解过程可以用下列式子归纳：
a[1]=1
a[i]=max{a[j]}+1 （i>1，j=1,2,…,i-1，且j同时要满足：a[j]>=a[i]）
最后，只需把a[1]~a[8]中的最大值输出即可。这就是第一问的解法，这种解题方法就称为“动态规划”。
第二问比较有意思。由于它紧接着第一问，所以很容易受前面的影响，多次采用第一问的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度序列“7 5 4 1 6 3 2”， 最长不上升序列为“7 5 4 3 2”，用多次求最长不上升序列的结果为3套系统；但其实只要2套，分别击落“7 5 4 1”与“6 3 2”。所以不能用“动态规划”做，那么，正确的做法又是什么呢？
我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要，上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种贪心算法，但贪心的策略不对。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，从拦截某个导弹所选的系统入手。
题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？当前瞄准高度较高的系统的“潜力”较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。
解题时用一个数组sys记下当前已有系统的各个当前瞄准高度，该数组中实际元素的个数就是第二问的解答。
[参考程序]
program noip1999_2;
const max=1000;
var i,j,current,maxlong,minheight,select,tail,total:longint;
height,longest,sys:array [1..max] of longint;
line:string;
begin
write('Input test data:');
readln(line); {输入用字符串}
i:=1;
total:=0; {飞来的导弹数}
while i<=length(line) do {分解出若干个数，存储在height数组中}
begin
while (i<=length(line)) and (line[i]=' ') do i:=i+1; {过滤空格}
current:=0; {记录一个导弹的高度}
while (i<=length(line)) and (line[i]<>' ') do {将一个字符串变成数}
begin
current:=current*10+ord(line[i])-ord('0');
i:=i+1
end;
total:=total+1;
height[total]:=current {存储在height中}
end;
longest[1]:=1; {以下用动态规划求第一问}
for i:=2 to total do
begin
maxlong:=1;
for j:=1 to i-1 do
begin
if height[i]<=height[j]
then if longest[j]+1>maxlong
then maxlong:=longest[j]+1;
longest[i]:=maxlong {以第i个导弹为结束，能拦截的最多导弹数}
end;
end;
maxlong:=longest[1];
for i:=2 to total do
if longest[i]>maxlong then maxlong:=longest[i];
writeln(maxlong); {输出第一问的结果}
sys[1]:=height[1]; {以下求第二问}
tail:=1; {数组下标，最后也就是所需系统数}
for i:=2 to total do
begin
minheight:=maxint;
for j:=1 to tail do {找一套最适合的系统}
if sys[j]>height[i] then
if sys[j]<minheight then
begin minheight:=sys[j]; select:=j end;
if minheight=maxint {开一套新系统}
then begin tail:=tail+1; sys[tail]:=height[i] end
else sys[select]:=height[i]
end;
writeln(tail)
end.
[部分测试数据]
输入1：300 250 275 252 200 138 245
输出1：
5
2
输入2：181 205 471 782 1033 1058 1111
输出2：
1
7
输入3：465 978 486 476 324 575 384 278 214 657 218 445 123
输出3：
7
4
输入4：236 865 858 565 545 445 455 656 844 735 638 652 659 714 845
输出4：
6
7
够详细的吧
B. 算法分析中动态规划的四个基本步骤
1、描述优解的结构特征。
2、递归地定义一个最优解的值。
3、自底向上计算一个最优解的值。
4、从已计算的信息中构造一个最优解。
C. 什么是动态规划
动态规划算法 概念及意义动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了着名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名着Dynamic Programming，这是该领域的第一本着作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型
多阶段决策过程的最优化问题。
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）
这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.
无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}
对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。
解决方法：
我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程 :
f1:=f(i-1,j+1); f2:=f(i-1,j);
if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];
显而易见，这个算法就是最简单的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的. 状态 决策
决策：
当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。
状态：
我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举.
动态规划算法的应用 一、动态规划的概念
近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。
要了解动态规划的概念，首先要知道什么是多阶段决策问题。
1. 多阶段决策问题
如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.
2．动态规划问题中的术语
阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。
在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。
过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。
当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。
无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
决策变量的范围称为允许决策集合。
策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。
给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。
最优性原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。
最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D，我们知道，最短路径是A�8�1B1�8�1C2�8�1D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A�8�1B1�8�1C2是A到C2的最短路径，B1�8�1C2�8�1D也是B1到D的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。
D. 什么是动态规划算法，常见的动态规划问题分析与求解
动态规划的题都是可以分出阶段的，比如背包问题可以由前i种物品的情况推导出前i+1种物品。 很多动态规划都是要求最优化某个值，有最优子结构性质，它的逻辑就是：要我求出前i+1种物品的最优值，
E. 详解动态规划算法
其实你可以这么去想。
能用动态规划解决的问题，肯定能用搜索解决。
但是搜素时间复杂度太高了，怎么优化呢？
你想到了记忆化搜索，就是搜完某个解之后把它保存起来，下一次搜到这个地方的时候，调用上一次的搜索出来的结果。这样就解决了处理重复状态的问题。
动态规划之所以速度快是因为解决了重复处理某个状态的问题。
记忆化搜索是动态规划的一种实现方法。
搜索到i状态，首先确定要解决i首先要解决什么状态。
那么那些状态必然可以转移给i状态。
于是你就确定了状态转移方程。
然后你需要确定边界条件。
将边界条件赋予初值。
此时就可以从前往后枚举状态进行状态转移拉。
F. 动态规划算法怎么计算
动态规划算法：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
（4）根据计算最优值时得到的信息，构造问题的最优解。
G. 分治算法和动态规划有什么不同和联系
一、分治法与动态规划主要共同点：
1）二者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小(小到很容易解决的程序)的子问题。然后将子问题的解合并，形成原问题的解。
二、分治法与动态规划实现方法：
① 分治法通常利用递归求解。
② 动态规划通常利用迭代法自底向上求解，但也能用具有记忆功能的递归法自顶向下求解。
三、分治法与动态规划主要区别：
① 分治法将分解后的子问题看成相互独立的。
② 动态规划将分解后的子问题理解为相互间有联系，有重叠部分。
H. 什么叫动态规划
动态规划的本质是递推或记忆化搜索。条件是无后效性和最优子结构性。空口说很难理解，LZ做一道DP的题目就理解了。
I. 动态规划算法的时间和空间复杂度是多少
动态规划算法一般是n步叠代计算局部最优解，每一步叠代需要计算m个子项，那么时间复杂度就是O(m*n)。如果只保存一步叠代的结果，空间复杂度就是O(m)；如果需要保存k步叠代结果，空间复杂度就是O(m*k)。