一、定义：
动态规划的过程是：每次的决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，利用这种多阶段最优化决策来解决问题的过程就是动态规划。
二、基本思想与策略：
首先将待求解的问题分解成若干个子问题，按顺序求解各个子问题，后一个问题的解需要依赖前一个问题的解。在求解任一子问题时，列出所有可能的局部解，通过决策保留那些可能达到最优决策的解，丢弃其他决策的局部解，依次解决各个子问题，最后一个子问题的解就是初始问题的解。
由于动态规划解决的问题，有重叠子问题的特点，为减少重复计算，每个子问题只计算一次，将其不同阶段的的不同状态保存在一个二维数组当中。
与分治法的区别是：适合用动态规划求解的问题，经分解后得到的子问题往往是不相互独立的，即下一个子问题的解需要依赖上一个子问题的解。
三、适用情况
能采用动态规划求解的问题一般有3个性质。
1、最优子结构性质。即问题的最优解中所包含的子问题的解也是最优的。
2、有重叠子问题。即子问题之间不独立，子问题之间有相互依赖性。
3、无后效性。即某阶段状态一旦确定，就不受这个状态以后决策的影响，也就是说，某状态以后的过程至于当前的状态有关。
四、求解步骤
动态规划所处理的问题是一个多阶段决策的问题，由初始状态开始，通过各个阶段决策的选择，到达最终的决策，即到了最后一个状态，这些决策过程形成了一个决策序列，同时确定了完成整个活动的一条路线，动态规划的模式如下：
初始状态------->决策1------->决策2------->.............------>决策n------->结束状态
1、 划分阶段。按照问题的时间或空间特征，把问题分成各个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
2、确定状态和状态变量。将问题发展到各个阶段时，所出现的各种状态都列出来，当然，状态的选择要满足后效性。
3、确定决策并写出状态转移方程。决策与状态转移之间有着密切的联系。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转移方程就可以写出来。但是，事实往往反过来做，根据相邻两个状态之间的关系，来确定决策方法和状态转移方程。
5、寻找边界条件。给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段，状态，状态转移决策，就可以写出状态转移方程（包括边界条件）。
实际应用中按照以下步骤：
1、分析最优解的性质，并刻画其结构特征。
2、递归定义最优解。
3、自底向上或自顶向下计算出最优值。
4、根据计算最优值得到的信息，构造问题的最优解。
三要素：问题的阶段、每个阶段的状态、从前一个状态到后一个状态之间的递推关系。
确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来表述，最优决策表是一个二维表，行表示决策的阶段，列表示问题的状态。表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从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;
}