一、基本概念
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
二、基本思想与策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
三、适用的情况
能采用动态规划求解的问题的一般要具有3个性质：
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
四、求解的基本步骤
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
图1 动态规划决策过程示意图
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
（4）根据计算最优值时得到的信息，构造问题的最优解
五、算法实现的说明
动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。
使用动态规划求解问题，最重要的就是确定动态规划三要素：
（1）问题的阶段 （2）每个阶段的状态
（3）从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。
确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}六、动态规划算法基本框架
for(j=1; j<=m; j=j+1) // 第一个阶段
xn[j] = 初始值;
for(i=n-1; i>=1; i=i-1) // 其他n-1个阶段
for(j=1; j>=f(i); j=j+1) //f(i)与i有关的表达式
xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案
print(x1[j1]);
for(i=2; i<=n-1; i=i+1）
{
t = t-xi-1[ji];
for(j=1; j>=f(i); j=j+1)
if(t=xi[ji])
break;
}Q1.数字金字塔
方法一：搜索
问题要求的是从最高点按照规则走到最低点的路径的最大的权值和，路径起点终点固定，走法规则明确，可以考虑用搜索来解决。
定义递归函数void Dfs(int x,int y,int Curr)，其中x,y表示当前已从(1,1)走到(x,y)，目前已走路径上的权值和为Curr。
当x=N时，到达递归出口，如果Curr比Ans大，则把Ans更新为Curr；否则向下一行两个位置行走，即递归执行Dfs(x+1,y,Curr+A[x+1][y])和Dfs(x+1,y+1,Curr+A[x+1][y+1])。
该方法实际上是把所有路径都走了一遍，由于每一条路径都是由N-1步组成，每一步有“左”、“右”两种选择，因此路径总数为2N-1，所以该方法的时间复杂度为O(2N-1)，超时。
方法二：记忆化搜索
方法一之所以会超时，是因为进行了重复搜索，如样例中从(1,1)到(3,2)有“左右”和“右左”两种不同的路径，也就是说搜索过程中两次到达(3,2)这个位置，那么从(3,2)走到终点的每一条路径就被搜索了两次，我们完全可以在第一次搜索(3,2)到终点的路径时就记录下(3,2)到终点的最大权值和，下次再次来到(3,2)时就可以直接调用这个权值避免重复搜索。我们把这种方法称为记忆化搜索。
记忆化搜索需要对方法一中的搜索进行改装。由于需要记录从一个点开始到终点的路径的最大权值和，因此我们重新定义递归函数Dfs。
定义Dfs(x,y)表示从(x,y)出发到终点的路径的最大权值和，答案就是Dfs(1,1)。计算Dfs(x,y)时考虑第一步是向左还是向右，我们把所有路径分成两大类：
①第一步向左：那么从(x,y)出发到终点的这类路径就被分成两个部分，先从(x,y)到(x+1,y)再从(x+1,y)到终点，第一部分固定权值就是A[x][y]，要使得这种情况的路径权值和最大，那么第二部分从(x+1,y)到终点的路径的权值和也要最大，这一部分与前面的Dfs(x,y)的定义十分相似，仅仅是参数不同，因此这一部分可以表示成Dfs(x+1,y)。综上，第一步向左的路径最大权值和为A[x][y]+Dfs(x+1,y)；
②第一步向右：这类路径要求先从(x,y)到(x+1,y+1)再从(x+1,y+1)到终点，分析方法与上面一样，这类路径最大权值和为A[x][y]+Dfs(x+1,y+1)；
为了避免重复搜索，我们开设全局数组F[x][y]记录从(x,y)出发到终点路径的最大权值和，一开始全部初始化为-1表示未被计算过。在计算Dfs(x,y)时，首先查询F[x][y]，如果F[x][y]不等于-1，说明Dfs(x,y)之前已经被计算过，直接返回 F[x][y]即可，否则计算出Dfs(x,y)的值并存储在F[x][y]中。
由于F[x][y]对于每个合法的(x,y)都只计算过一次，而且计算是在O(1)内完成的，因此时间复杂度为O(N2)。可以通过本题。方法三：动态规划(顺推法)
方法二通过分析搜索的状态重复调用自然过渡到记忆化搜索，而记忆化搜索本质上已经是动态规划了。下面我们完全从动态规划的算法出发换一个角度给大家展示一下动态规划的解题过程，并提供动态规划的迭代实现法。 ①确定状态：
题目要求从(1,1)出发到最底层路径最大权值和，路径中是各个点串联而成，路径起点固定，终点和中间点相对不固定。因此定义F[x][y]表示从(1,1)出发到达(x,y)的路径最大权值和。最终答案Ans=max{F[N][1],F[N][2],...,F[N][N]}。 ②确定状态转移方程和边界条件：
不去考虑(1,1)到(x,y)的每一步是如何走的，只考虑最后一步是如何走，根据最后一步是向左还是向右分成以下两种情况：
向左：最后一步是从(x-1,y)走到(x,y),此类路径被分割成两部分，第一部分是从(1,1)走到(x-1,y)，第二部分是从(x-1,y)走到(x,y)，要计算此类路径的最大权值和，必须用到第一部分的最大权值和，此部分问题的性质与F[x][y]的定义一样，就是F[x-1,y]，第二部分就是A[x][y]，两部分相加即得到此类路径的最大权值和为F[x-1,y]+A[x,y]；
向右：最后一步是从(x-1,y-1)走到(x,y),此类路径被分割成两部分，第一部分是从(1,1)走到(x-1,y-1)，第二部分是从(x-1,y-1)走到(x,y)，分析方法如上。此类路径的最大权值和为F[x-1,y-1]+A[x,y]；
F[x][y]的计算需要求出上面两种情况的最大值。综上，得到状态转移方程如下：
F[x][y]=max{F[x-1,y-1],F[x-1][y]}+A[x,y]
与递归关系式还需要递归终止条件一样，这里我们需要对边界进行处理以防无限递归下去。观察发现计算F[x][y]时需要用到F[x-1][y-1]和F[x-1,y]，是上一行的元素，随着递归的深入，最终都要用到第一行的元素F[1][1],F[1][1]的计算不能再使用状态转移方程来求，而是应该直接赋予一个特值A[1][1]。这就是边界条件。 综上得：
状态转移方程：F[x][y]=max{F[x-1][y-1],F[x-1][y]}+A[x,y]
边界条件：F[1][1]=A[1][1]
现在让我们来分析一下该动态规划的正确性，分析该解法是否满足使用动态规划的两个前提：
最优化原理：这个在分析状态转移方程时已经分析得比较透彻，明显是符合最优化原理的；
无后效性：状态转移方程中，我们只关心F[x-1][y-1]与F[x-1][y]的值，计算F[x-1][y-1]时可能有多种不同的决策对应着最优值，选哪种决策对计算F[x][y]的决策没有影响，F[x-1][y]也是一样。这就是无后效性。
③程序实现：
由于状态转移方程就是递归关系式，边界条件就是递归终止条件，所以可以用递归来完成，递归存在重复调用，利用记忆化可以解决重复调用的问题，方法二已经讲过。记忆化实现比较简单，而且不会计算无用状态，但递归也会受到“栈的大小”和“递推+回归执行方式”的约束，另外记忆化实现调用状态的顺序是按照实际需求而展开，没有大局规划，不利于进一步优化。
这里介绍一种迭代法。与分析边界条件方法相似，计算F[x][y]用到状态F[x-1][y-1]与F[x-1][y]，这些元素在F[x][y]的上一行，也就是说要计算第x行的状态的值，必须要先把第x-1行元素的值计算出来，因此我们可以先把第一行元素F[1][1]赋为 A[1][1]，再从第二行开始按照行递增的顺序计算出每一行的有效状态即可。时间复杂度为O(N2)。 方法四：动态规划(逆推法)
【算法分析】
①贪心法往往得不到最优解：本题若采用贪心法则：13-11-12-14-13，其和为63,但存在另一条路：13-8-26-15-24，其和为86。
贪心法问题所在：眼光短浅。
②动态规划求解：动态规划求解问题的过程归纳为：自顶向下的分析，自底向上计算。
其基本方法是：
划分阶段：按三角形的行，划分阶段，若有n行，则有n-1个阶段。
A．从根结点13出发，选取它的两个方向中的一条支路，当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。
B．自底向上计算：（给出递推式和终止条件）
①从底层开始，本身数即为最大数；
②倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32；
③倒数第三层的计算，取决于底二层计算的数据：27+12=39，39+7=46，39+26=65
④倒数第四层的计算，取决于底三层计算的数据：46+11=57，65+8=73
⑤最后的路径：13——8——26——15——24
C．数据结构及算法设计
①图形转化：直角三角形，便于搜索：向下、向右
②用三维数组表示数塔：a[x][y][1]表示行、列及结点本身数据,a[x][y][2]能够取得最大值,a[x][y][3]表示前进的方向——0向下，1向右；
③算法：
数组初始化，输入每个结点值及初始的最大路径、前进方向为0；
从倒数第二层开始向上一层求最大路径，共循环N-1次；
从顶向下，输出路径：究竟向下还是向右取决于列的值，若列的值比原先多1则向右，否则向下。
Q2.求最长不下降序列
㈠问题描述：
设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j) (i<>j)，若存在i1<i2<i3< … < ie 且有b(i1)<b(i2)< … <b(ie)则称为长度为e的不下降序列。当原数列出之后，求出最长的不下降序列。
例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63长度为8的不下降序列。
㈡算法分析：
根据动态规划的原理，由后往前进行搜索(当然从前往后也一样)。
1·对b(n)来说，由于它是最后一个数，所以当从b(n)开始查找时，只存在长度为1的不下降序列；
2·若从b(n-1)开始查找，则存在下面的两种可能性：
①若b(n-1)<b(n)则存在长度为2的不下降序列b(n-1)，b(n)。
②若b(n-1)>b(n)则存在长度为1的不下降序列b(n-1)或b(n)。
3·一般若从b(i)开始，此时最长不下降序列应该按下列方法求出:
在b(i+1),b(i+2),…,b(n)中，找出一个比b(i)大的且最长的不下降序列，作为它的后继。
㈢数据结构：
为算法上的需要，定义一个整数类型二维数组b(N,3)
1·b(I,1)表示第I个数的数值本身；
2·b(I,2)表示从I位置到达N的最长不下降序列长度
3·b(I,3)表示从I位置开始最长不下降序列的下一个位置，若b[I,3]=0则表示后面没有连接项。
㈣求解过程：
①从倒数第二项开始计算，后面仅有1项，比较一次，因63>15，不符合要求，长度仍为1。
②从倒数第三项开始其后有2项，需做两次比较，得到目前最长的不下降序列为2，如下表：
| 11 | 12 | 13 | 14 | …… | 11 | 12 | 13 | 14 | ||
| 22 | 63 | 15 | …… | 21 | 22 | 63 | 15 | |||
| 2 | 1 | 1 | …… | 3 | 2 | 1 | 1 | |||
| 13 | 0 | 0 | …… | 12 | 13 | 0 | 0 |
㈤一般处理过程是：
①在i+1,i+2,…,n项中，找出比b[I,1]大的最长长度L以及位置K;
②若L>0，则b[I,2]:=L+1;b[I,3]:=k;
最后本题经过计算，其数据存储表如下：| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 13 | 7 | 9 | 16 | 38 | 24 | 37 | 18 | 44 | 19 | 21 | 22 | 63 | 15 |
| 7 | 8 | 7 | 6 | 3 | 4 | 3 | 5 | 2 | 4 | 3 | 2 | 1 | 1 |
| 4 | 3 | 4 | 8 | 9 | 7 | 9 | 10 | 13 | 11 | 12 | 13 | 0 | 0 |
Q3.拦截导弹
【算法分析】
第一问即经典的最长不下降子序列问题，可以用一般的DP算法，也可以用高效算法，但这个题的数据规模不需要。
用a[x]表示原序列中第x个元素，b[x]表示长度为x的不下降子序列的长度，当处理第a[x]时，可查找它可以连接到长度最大为多少的不下降子序列后（即与部分b[x]比较）。假设可以连到长度最大为maxx的不下降子序列后，则b[x]:=maxx+1。b数组被赋值的最大值就是第一问的答案。
第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。
Q4.城市交通路网
Q5.挖地雷
【算法分析】
本题是一个经典的动态规划问题。很明显，题目规定所有路径都是单向的，所以满足无后效性原则和最优化原理。设W[i]为第i个地窖所藏有的地雷数，A[i][j]表示第i个地窖与第j个地窖之间是否有通路，F[i]为从第i个地窖开始最多可以挖出的地雷数，则有如下递归式：
F[i]=max{ W[i]+ F[j]} (i<j<=n , A[i][j]=true)
边界：F[n]=W[n]
于是就可以通过递推的方法，从后F(n)往前逐个找出所有的F[i]，再从中找一个最大的即为问题2的解。对于具体所走的路径（问题1），可以通过一个向后的链接来实现。