下载文档原格式
动态规划的具体应用例题3.1 最长不降子序列（1）问题描述设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)例如3，18，7，14，10，12，23，41，16，24。
若存在i1<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。
如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。
程序要求，当原数列给出之后，求出最长的不下降序列。
（2）算法分析根据动态规划的原理，由后往前进行搜索。
1· 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；2· 若从a(n-1)开始查找，则存在下面的两种可能性：①若a(n-1)<a(n)则存在长度为2的不下降序列a(n-1)，a(n)。
②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。
3· 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出: 在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。
4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号(3) 程序如下:（逆推法）program li1;const maxn=100;var a,b,c:array[1..maxn] of integer;fname:string;f:text;n,i,j,max,p:integer;beginreadln(fname);assign(f,fname);reset(f);readln(f,n);+for i:=1 to n dobeginread(f,a[i]);b[n]:=1;c[n]:=0;end;for i:= n-1 downto 1 dobeginmax:=0;p:=0;for j:=i+1 to n doif (a[i]<a[j]) and (b[j]>max) then begin max:=b[j];p:=j end;if p<>0 then begin b[i]:=b[p]+1;c[i]:=p endend;max:=0;p:=0;for i:=1 to n doif b[i]>max then begin max:=b[i];p:=i end;writeln('maxlong=',max);write('result is:');while p<>0 dobegin write(a[p]:5);p:=c[p] end;end.3.2 背包问题背包问题有三种1.部分背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。
动态规划运筹学例题动态规划是运筹学中常用的一种优化技术，它利用规划、三角函数和其他数学技术来解决日常生活中的各种问题，比如最优路线问题、最优资源分配问题、最优出行路线问题等。
本文将通过一个例题，来介绍动态规划的基本思想，以及如何利用动态规划来解决问题。
例题一：已知一条路线，由A点到B点，有N个途经的节点，每个节点之间的距离已知。
求从A到B的最短路线。
按照动态规划的思想，首先将该问题分解为若干个子问题，并根据子问题的解来解决原问题，这种分解和解决问题的方式称为动态规划。
对于上面的问题，可以将其分解为N个子问题，分别是从A到第1个节点、从第1个节点到第2个节点、从第2个节点到第3个节点，以此类推，最后一个子问题是从第N-1个节点到B点的最短路程。
将上面的N个子问题中，从第i个节点到B点的最短路程记为d[i]，由于从第i个节点到B点可能经过i+1、i+2、……、N-1节点，因此要找到d[i]，只需要找到经过i+1、i+2、……、N-1节点的最短路程即可，即求d[i]=Min{d[i+1]+length[i][i+1],d[i+2]+length[i][i+2],…,d[N-1]+length[i][N-1]}，其中length[i][j]是第i个节点到第j个节点的距离。
以上就是动态规划的解题步骤，它能将原问题分解成若干个子问题，并找到最优解。
对于本例来说，通过上述步骤，就可以得到从A 到B的最短路程。
这种分解和求解问题的方法是动态规划，可以用来解决许多类似的问题，如：1）最优路线问题；2）旅行推销员问题；3）硬币找零问题。
动态规划的一大特点是，他能很好地将问题分解为多个子问题，并能从子问题的解中求解出最优解。
总之，动态规划是一种很有用的优化技术，它可以有效解决各种运筹学问题。
它不仅可以帮助我们解决许多具体问题，而且还能使我们更好地理解问题及其解法。
动态规划例题动态规划是一种以最优化原理为基础的问题求解方法，通过拆分问题为若干阶段，每个阶段求解一个子问题，再逐步推导出整个问题的最优解。
例如，有一个背包能够承受一定的重量，现有一些物品，每个物品都有自己的重量和价值。
我们希望将物品放入背包中，使得背包的总价值最大。
这个问题可以用动态规划来解决。
首先，我们定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，容量为j的背包中所能放入的物品的最大价值。
那么，对于每一个物品，可以选择放入背包或者不放入背包。
如果选择放入背包，最大价值为dp[i-1][j-w[i]] + v[i]，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。
如果选择不放入背包，最大价值为dp[i-1][j]。
因此，dp[i][j]的状态转移方程为：dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j])。
基于这个状态转移方程，可以逐步求解从第1个物品到第n个物品的最大价值。
最终，dp[n][W]即为问题的最优解，其中W 表示背包的容量。
举个简单的例子，假设背包的容量为10，有3个物品，它们的重量分别为3、4、5，价值分别为4、5、6。
此时，可以得到如下的dp矩阵：0 0 0 0 0 0 0 0 0 0 00 0 0 4 4 4 4 4 4 4 40 0 0 4 5 5 9 9 9 9 90 0 0 4 5 5 9 10 10 14 14我们可以看到，dp[3][10]的最大价值为14，表示在前3个物品中，容量为10的背包中所能放入的物品的最大价值为14。
通过动态规划，我们可以有效地求解背包问题，得到物品放入背包的最优解。
这个例子只是动态规划的一个简单应用，实际上，动态规划可以解决各种复杂的问题，如最长公共子序列、最大子数组和、最大字段和等。
因此，学习动态规划是非常有意义的。
动态规划典型案例解析及计算过程梳理动态规划（Dynamic Programming）是一种通过将问题分解为子问题来解决复杂问题的算法策略。
它通常用于优化问题，通过将问题的解决方案划分为相互重叠的子问题来降低计算复杂度。
下面将通过几个典型案例，详细解析动态规划的应用及其计算过程。
1. 斐波那契数列斐波那契数列是一种经典的动态规划问题。
它的定义是：F(n) =F(n-1) + F(n-2)，其中F(0) = 0，F(1) = 1。
我们需要计算第n个斐波那契数。
通过动态规划的思想，可以将该问题划分为子问题，即计算第n-1和第n-2个斐波那契数。
可以使用一个数组来保存已经计算过的斐波那契数，避免重复计算。
具体的计算过程如下：1. 初始化一个长度为n+1的数组fib，将fib[0]设置为0，fib[1]设置为1。
2. 从i=2开始遍历到n，对于每个i，计算fib[i] = fib[i-1] + fib[i-2]。
3. 返回fib[n]作为结果。
通过上述过程，我们可以快速地得到第n个斐波那契数。
这个案例展示了动态规划的重要特性，即将问题分解为子问题进行求解，并利用已经计算过的结果来避免重复计算。
2. 背包问题背包问题是另一个常见的动态规划问题。
问题的定义是：有一组物品，每个物品有自己的重量和价值，在限定的背包容量下，如何选择物品使得背包中的总价值最大化。
通过动态规划的思想，背包问题可以被划分为子问题。
我们可以定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，背包容量为j时的最大价值。
具体的计算过程如下：1. 初始化一个大小为n+1行，m+1列的二维数组dp，其中n为物品数量，m为背包容量。
将所有元素初始化为0。
2. 从i=1开始遍历到n，对于每个i，从j=1开始遍历到m，对于每个j，进行如下判断：- 若当前物品的重量大于背包容量j，则dp[i][j] = dp[i-1][j]，即不选择当前物品；- 若当前物品的重量小于等于背包容量j，则dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)，即选择当前物品或不选择当前物品所能获得的最大价值。
动态规划练习题[题1] 多米诺骨牌（DOMINO）问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。
现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。
顶行和底行的差值是2。
这个差值是两行点数之和的差的绝对值。
每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。
现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。
对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。
输入格式：文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。
接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。
第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。
输出格式：只有一个整数在文件的第一行。
这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。
[题2] Perform巡回演出题目描述:Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去.每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.输出:对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.样例输入: 样例输出：3 6 4602 130 150 03 75 0 807 120 110 0 100 110 120 04 60 70 60 503 0 135 1402 70 802 32 0 701 800 0[题3] 复制书稿（BOOKS）问题描述：假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，…PM）。
动态规划总结——经典问题总结本文着重讨论状态是如何表示，以及方程是怎样表示的。
当然，还附上关键的，有可能作为模板的代码段。
但有的代码的实现是优化版的。
经典问题总结最长上升子序列（LIS）问题描述如下:设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。
求最大的m值。
这里采用的是逆向思维的方法，从最后一个开始想起，即先从A[N]（A数组是存放数据的数组，下同）开始，则只有长度为1的子序列，到A[N-1]时就有两种情况，如果a[n-1] < a[n] 则存在长度为2的不下降子序列a[n-1],a[n]；如果a[n-1] > a[n] 则存在长度为1的不下降子序列a[n-1]或者a[n]。
有了以上的思想，DP方程就呼之欲出了（这里是顺序推的，不是逆序的）：DP[I]=MAX（1,DP[J]+1）J=0,1,...,I-1但这样的想法实现起来是）O(n^2)的。
本题还有更好的解法，就是O(n*logn)。
利用了长升子序列的性质来优化，以下是优化版的代码：//最长不降子序const int SIZE=500001;int data[SIZE];int dp[SIZE];//返回值是最长不降子序列的最大长度,复杂度O(N*logN)int LCS(int n) { //N是DATA数组的长度,下标从1开始int len(1),low,high,mid,i;dp[1]=data[1];for(i=1;i<=n;++i) {low=1;high=len;while( low<=high ) { //二分mid=(low+high)/2;if( data[i]>dp[mid] ) {low=mid+1;}else {high=mid-1;}}dp[low]=data[i];if( low>len ) {++len;}}return len;}最长公共子序列（LCS）给出两个字符串a, b，求它们的最长、连续的公共字串。
动态规划详解（C++版）动态规划一、背包问题：01背包问题题目有N件物品和一个容积为V的背包。
第i件物品的体积是c[i]，价值是w[i]。
求解将哪些物品装入背包可使价值总和最大。
基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v 的背包可以获得的最大价值。
则其状态转移方程便是：二维方程：f[i,v]:=max(f[i-1,v],f[i-1,v-c[i]]+w[i])一维方程：f[v]:=max(f[v],f[v-c[i]]+w[i]);这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品放或不放，那么就可以转化为一个只牵扯前i-1件物品的问题。
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
1．采药(RQNOJ15)；题目描述：辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。
医师为了判断他的资质，给他出了一个难题。
医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。
如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。
”如果你是辰辰，你能完成这个任务吗？输入格式：输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
动态规划算法详解及经典例题⼀、基本概念（1）⼀种使⽤多阶段决策过程最优的通⽤⽅法。
（2）动态规划过程是：每次决策依赖于当前状态，⼜随即引起状态的转移。
⼀个决策序列就是在变化的状态中产⽣出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
假设问题是由交叠的⼦问题所构成，我们就能够⽤动态规划技术来解决它。
⼀般来说，这种⼦问题出⾃对给定问题求解的递推关系中，这个递推关系包括了同样问题的更⼩⼦问题的解。
动态规划法建议，与其对交叠⼦问题⼀次重新的求解，不如把每⼀个较⼩⼦问题仅仅求解⼀次并把结果记录在表中（动态规划也是空间换时间的）。
这样就能够从表中得到原始问题的解。
（3）动态规划经常常使⽤于解决最优化问题，这些问题多表现为多阶段决策。
关于多阶段决策：在实际中，⼈们经常遇到这样⼀类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若⼲个联系的阶段。
⽽在各阶段中。
⼈们都须要作出⽅案的选择。
我们称之为决策。
⽽且当⼀个阶段的决策之后，经常影响到下⼀个阶段的决策，从⽽影响整个过程的活动。
这样，各个阶段所确定的决策就构成⼀个决策序列，常称之为策略。
因为各个阶段可供选择的决策往往不⽌⼀个。
因⽽就可能有很多决策以供选择，这些可供选择的策略构成⼀个集合，我们称之为同意策略集合（简称策略集合）。
每⼀个策略都对应地确定⼀种活动的效果。
我们假定这个效果能够⽤数量来衡量。
因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择⼀个策略，使其在预定的标准下达到最好的效果。
经常是⼈们所关⼼的问题。
我们称这种策略为最优策略，这类问题就称为多阶段决策问题。
（4）多阶段决策问题举例：机器负荷分配问题某种机器能够在⾼低两种不同的负荷下进⾏⽣产。
在⾼负荷下⽣产时。
产品的年产量g和投⼊⽣产的机器数量x的关系为g=g(x)，这时的年完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0<a<1)；在低负荷下⽣产时，产品的年产量h和投⼊⽣产的机器数量y的关系为h=h(y)。
动态规划讲解大全动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。
例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。
不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。
动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。
因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。
我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
基本模型多阶段决策过程的最优化问题。
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。
当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。
记忆化搜索给你一个数字三角形, 形式如下:12 34 5 67 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];显而易见，这个算法就是最简单的搜索算法。
时间复杂度为2n，明显是会超时的。
分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。
为了避免浪费，很显然，我们存放一个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阶段的状态转移规律，称为状态转移方程。
最优性原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。
D也是B1到D的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。
◊C2◊C2是A到C2的最短路径，B1◊B1◊D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A◊C2◊B1◊最优性原理实际上是要求问题的最优策略的子策略也是最优。
让我们通过对前面的例子再分析来具体说明这一点：从A到D，我们知道，最短路径是A动态规划练习题USACO 2.2 Subset Sums题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。
举个例子，如果N=3，对于{1，2，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: subsetINPUT FORMAT输入文件只有一行，且只有一个整数NSAMPLE INPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数，如果不存在则输出0。
SAMPLE OUTPUT (file subset.out)4参考程序如下：#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题目如下：在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。
