pascal 动态规划

Question

pascal 中什么是动态规划

Answer 1

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱.
　　动态规划首次进入信息学奥赛是在IOI94（数字三角形），在国内首次出现是在NOI95。此后动态规划成为信息学奥赛的必考算法之一。
编辑本段
分类

　　动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
　　举例
线性动规
　　拦截导弹，合唱队形，挖地雷等
区域动规
　　石子合并， 加分二叉树，统计单词个数等
树形动规
　　贪吃的九头龙，二分查找树等
背包问题
　　装箱问题，挤牛奶（同济ACM第1132题）等
编辑本段
概念及意义

　　动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
　　虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
　　动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
编辑本段
基本模型

　　多阶段决策过程的最优化问题。
　　含有递推的思想以及各种数学原理（加法原理，乘法原理等等）。
　　在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 多阶段决策问题这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。
编辑本段
基本思想

　　动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
编辑本段
基本结构

　　多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。
　　动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划，可以解决各类最优化问题。因此在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。
编辑本段
基本模型

　　根据上例分析和动态规划的基本概念，可以得到动态规划的基本模型如下：
　　(1)确定问题的决策对象。 (2)对决策过程划分阶段。 (3)对各阶段确定状态变量。 (4)根据状态变量确定费用函数和目标函数。 (5)建立各阶段状态变量的转移过程，确定状态转移方程。
编辑本段
适用条件

　　任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
　　1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
　　2.无后效性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
　　3.子问题的重叠性 动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。 动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
编辑本段
作用

　　在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。
记忆化搜索
　　给你一个数字三角形, 形式如下:
　　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=f2+a[i,j]; else f=f1+a[i,j];
　　显而易见，这个算法就是最简单的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.
　　并且记忆搜索占的内存相对来说较少
　　计算核心片段：
　　for(int i = n-1; i >= 1; --i) //从倒数第二行开始
　　{
　　for(int j=1; j <= i; j++)
　　{
　　if (a[i+1][j][1] > a[i+1][j+1][1]) //左边大
　　{
　　a[i][j][2] = 0; //选择左边
　　a[i][j][1] += a[i+1][j][1];
　　}
　　else //右边大
　　{
　　a[i][j][2] = 1; //选择右边
　　a[i][j][1] += a[i+1][j+1][1];
　　}
　　}
　　}
决策
　　决策：
　　当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。
状态
　　状态：
　　我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举.
　　
编辑本段
应用

　　一、动态规划的概念
　　　近年来，涉及动态规划的各种竞赛题越来越多，每一年的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B1C2D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优： 最优化原理AB1C2是A到C2的最短路径，B1C2D也是B1到D的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。
编辑本段
动态规划练习题

　　USACO
　　2.2 Subset Sums
　　题目如下：
　　对于从1到N的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。
　　举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：
　　{3}and {1,2}
　　这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）
　　如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:
　　{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
　　{2,5,7} and {1,3,4,6}
　　{3,4,7} and {1,2,5,6}
　　{1,2,4,7} and {3,5,6}
　　给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。
　　PROGRAM NAME: subset
　　INPUT FORMAT
　　输入文件只有一行，且只有一个整数N
　　SAMPLE INPUT (file subset . in)
　　7
　　OUTPUT FORMAT
　　输出划分方案总数，如果不存在则输出0。
　　SAMPLE OUTPUT (file subset.out)
　　4
　　参考程序如下（C++语言）：
　　#include <fstream>
　　using namespace std;
　　const unsigned int MAX_SUM = 1024;
　　int n;
　　unsigned long long int dyn[MAX_SUM];
　　ifstream fin ("subset. in");
　　ofstream fout ("subset.out");
　　int main() {
　　fin >> n;
　　fin.close();
　　int s = n*(n+1);
　　if (s % 4) {
　　fout << 0 << endl;
　　fout.close ();
　　return ;
　　}
　　s /= 4;
　　int i, j;
　　dyn [0] = 1;
　　for (i = 1; i <= n; i++)
　　for (j = s; j >= i; j--)
　　dyn[j] += dyn[j-i];
　　fout << (dyn[s]/2) << endl;
　　fout.close();
　　return 0;
　　}
　　USACO 2.3
　　Longest Prefix
　　题目如下：
　　在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。
　　如果一个集合 P 中的元素可以通过并运算（允许重复；并，即∪，相当于 Pascal 中的 “+” 运算符）组成一个序列 S ，那么我们认为序列 S 可以分解为 P 中的元素。并不是所有的元素都必须出现。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：
　　{A, AB, BA, CA, BBC}
　　序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。
　　PROGRAM NAME: prefix
　　INPUT FORMAT
　　输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ，长度为 1..200,000 ，用一行或者多行的字符串来表示，每行不超过 76 个字符。换行符并不是序列 S 的一部分。
　　SAMPLE INPUT (file prefix. in)
　　A AB BA CA BBC
　　.
　　ABABACABAABC
　　OUTPUT FORMAT
　　只有一行，输出一个整数，表示 S 能够分解成 P 中元素的最长前缀的长度。
　　SAMPLE OUTPUT (file prefix.out)
　　11
　　示例程序如下：
　　#include <stdio.h>
　　/* maximum number of primitives */
　　#define MAXP 200
　　/* maximum length of a primitive */
　　#define MAXL 10
　　char prim[MAXP+1][MAXL+1]; /* primitives */
　　int nump; /* number of primitives */
　　int start[200001]; /* is this prefix of the sequence expressible? */
　　char data[200000]; /* the sequence */
　　int ndata; /* length of the sequence */
　　int main(int argc, char **argv)
　　{
　　FILE *fout, *fin;
　　int best;
　　int lv, lv2, lv3;
　　if ((fin = fopen("prim. in", "r")) == NULL)
　　{
　　perror ("fopen fin");
　　exit(1);
　　}
　　if ((fout = fopen("prim.out", "w")) == NULL)
　　{
　　perror ("fopen fout");
　　exit(1);
　　}
　　/* read in primitives */
　　while (1)
　　{
　　fscanf (fin, "%s", prim[nump]);
　　if (prim[nump][0] != '.') nump++;
　　else break;
　　}
　　/* read in string, one line at a time */
　　ndata = 0;
　　while (fscanf (fin, "%s", data+ndata) == 1)
　　ndata += strlen(data+ndata);
　　start[0] = 1;
　　best = 0;
　　for (lv = 0; lv < ndata; lv++)
　　if (start[lv])
　　{ /* for each expressible prefix */
　　best = lv; /* we found a longer expressible prefix! */
　　/* for each primitive, determine the the sequence starting at
　　this location matches it */
　　for (lv2 = 0; lv2 < nump; lv2++)
　　{
　　for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] &&
　　prim[lv2][lv3] == data[lv+lv3]; lv3++)
　　;
　　if (!prim[lv2][lv3]) /* it matched! */
　　start[lv + lv3] = 1; /* so the expanded prefix is also expressive */
　　}
　　}
　　/* see if the entire sequence is expressible */
　　if (start[ndata]) best = ndata;
　　fprintf (fout, "%i\n", best);
　　return 0;
　　}
　　USACO 3.1
　　Score Inflation
　　题目如下：
　　我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。
　　我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。
　　你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。
　　输入包括竞赛的时间,M(1 <= M <= 10,000)和N,"种类"的数目1 <= N <= 10,000。
　　后面的每一行将包括两个整数来描述一个"种类":
　　第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。
　　你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。
　　来自任意的"种类"的题目数目可能任何非负数(0或更多)。
　　计算可能得到的最大分数。
　　PROGRAM NAME: inflate
　　INPUT FORMAT
　　第 1 行: M, N--竞赛的时间和题目"种类"的数目。
　　第 2-N+1 行: 两个整数:每个"种类"题目的分数和耗时。
　　SAMPLE INPUT (file inflate .in)
　　300 4
　　100 60
　　250 120
　　120 100
　　35 20
　　OUTPUT FORMAT
　　单独的一行包括那个在给定的限制里可能得到的最大的分数。
　　SAMPLE OUTPUT (file inflate.out)
　　605
　　{从第2个"种类"中选两题，第4个"种类"中选三题}
　　示例程序如下：
　　#include <fstream.h>
　　ifstream fin("inflate .in");
　　ofstream fout("inflate.out");
　　const short maxm = 10010;
　　long best[maxm], m, n;
　　void
　　main()
　　{
　　short i, j, len, pts;
　　fin >> m >> n;
　　for (j = 0; j <= m; j++)
　　best[j] = 0;
　　for (i = 0; i < n; i++) {
　　fin >> pts >> len;
　　for (j = len; j <= m; j++)
　　if (best[j-len] + pts > best[j])
　　best[j] = best[j-len] + pts;
　　}
　　fout << best[m] << endl; // 由于数组元素不减，末元素最大
　　}
　　USACO 3.3
　　A Game
　　题目如下：
　　有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。
　　编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。
　　PROGRAM NAME: game1
　　INPUT FORMAT
　　第一行: 正整数N, 表示序列中正整数的个数。
　　第二行至末尾: 用空格分隔的N个正整数（大小为1-200）。
　　SAMPLE INPUT (file game1.in)
　　6
　　4 7 2 9
　　5 2
　　OUTPUT FORMAT
　　只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。
　　SAMPLE OUTPUT (file game1.out)
　　18 11
　　参考程序如下：
　　#include <stdio.h>
　　#define NMAX 101
　　int best[NMAX][2], t[NMAX];
　　int n;
　　void
　　readx () {
　　int i, aux;
　　freopen ("game1.in", "r", stdin);
　　scanf ("%d", &n);
　　for (i = 1; i <= n; i++) {
　　scanf ("%d", &aux);
　　t= t[i - 1] + aux;
　　}
　　fclose (stdin);
　　}
　　inline int
　　min (int x, int y) {
　　return x > y ? y : x;
　　}
　　void
　　solve () {
　　int i, l;
　　for (l = 1; l <= n; l++)
　　for (i = 1; i + l <= n + 1; i++)
　　best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
　　best[(l - 1) % 2]);
　　}
　　void writex () {
　　freopen ("game1.out", "w", stdout);
　　printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
　　fclose (stdout);
　　}
　　int
　　main () {
　　readx ();
　　solve ();
　　writex ();
　　return 0;
　　}
　　USACO 3.4
　　Raucous Rockers

Answer 2

算法的一种，是用来解决最优化问题的。简单的说就是做到每一步都是最优的

Answer 3

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

动态规划满足的条件：
1、一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。
2、无后效性
“过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵。

动态规划的一般模式：
1、划分阶段
按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的，否则问题就无法求解。
2、选择状态
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
3、确定决策并写出状态转移方程
之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
4、写出规划方程（包括边界条件）：
一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。

动态规划的实现方法：
递推（正向）
递归回溯（反向）

常见模型分析：
1、线性模型（如最长上升子序列、矿工配餐问题、平衡花园问题等）
线性模型是最容易导致动态规划算法的，只要把线性结构分成两部分，往往就能用递归来解决。
2、字符串模型
字符串模型也是一种线性模型，但是由于串有特殊的“匹配”、“取前缀后缀”操作，因此很多情况下他们的模型具有一些一般线性结构所没有的特点
3、区间模型（如NOI2009二叉查找树）
这一类题目的关键是用区间来表示状态，并建立合理的状态转移
4、状态压缩模型（如NOI2001 炮兵阵地、NOI2007生成树计数、WC2008游览计划等）
有时候，虽然无法得到多项式算法，但是由于充分利用重叠子问题，仍然可以得到满意的算法。
状态压缩型动态规划往往有一个维度特别小，然后就可以压缩该维度
5、树状模型（如NOI2006网络收费、NOI2008设计路线等）
树本来就是一种递归结构，因此很多情况下都可以用动态规划来解决
6、环状模型

动态规划的时间复杂度:
状态数目 * 状态转移时间复杂度

动态规划的优化方向:
减少状态数目
提高状态转移效率

Answer 4

不知道