文章目录
1.序
2.动态规划的基本概念[^1]
3.动态规划算法的基本思想[^2]
4.动态规划的求解步骤[^2]
5.动态规划算法的基本要素[^2]
5.1 最优子结构
5.2 重叠子问题
6.一些经典的动态规划问题

1.序
近期笔者会写一些博客，与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。
2.动态规划的基本概念[^1]
在学习动态规划之前，先思考这样一个问题：什么是动态规划？为什么叫动态规划？

当读者在试图探索这个问题的时候，不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的，应用于工程领域。

动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。
所谓多阶段决策过程是指这样一类决策过程：它可以把一一个复杂问题按时间(或空间)分成若干个阶段，每个阶段都需要作出决策，
以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何，不但与该阶段的经济效果有关，
还影响以后各阶段的经济效果，可见这类多阶段决策问题是一个动态的问题，因此，处理的方法称为动态规划方法。然而，动态
规划也可以处理一些本来与时间没有关系的静态模型，这只要在静态模型中人为地引入“时间”因素，分成时段，就可以把它看作
是多阶段的动态模型，用动态规划方法去处理。

简言之，多阶段决策过程是指这样的一类特殊的活动过程：问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。

下面举例说明什么是多阶段决策问题。

例1（最短路线问题）在线路网络图1中，从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离，为使总运费最少，必须找出一条由A至E总里程最短的路线。

图1

为了找到由A至E的最短线路，可以将该问题分成A—B—C—D—E 4个阶段，在每个阶段都需要作出决策，即在A点需决策下一步到B1还是到B2或B3；同样，若到达第二阶段某个状态，比如B1 ，需决定走向C1还是C2 ；依次类推，可以看出：各个阶段的决策不同，由A至E的路线就不同，当从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离，而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条路线对应的总路程最短。

3.动态规划算法的基本思想[^2]
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。

图2

但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。


图3
4.动态规划的求解步骤[^2]
a. 找出最优解的性质，并刻划其结构特征。

b. 递归地定义最优值。

c. 以自底向上的方式计算出最优值。

d. 根据计算最优值时得到的信息，构造最优解
5.动态规划算法的基本要素[^2]
5.1 最优子结构

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
5.2 重叠子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

图4

6.一些经典的动态规划问题
这部分待补充~

笔者要充电了~
参考文献

[1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html

[2]引用自老师的课件

动态规划算法介绍 
1)动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法 
2)动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 
3)与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4)动态规划可以通过填表的方式来逐步推进，得到最优解. 
应用场景-背包问题 
背包问题：有一个背包，容量为4磅 ， 现有如下物品 
1)要求达到的目标为装入的背包的总价值最大，并且重量不超出 
2)要求装入的物品不能重复 
代码实现：
package com.dynamic;
import java.util.Arrays;
public class PackageProblem {
	public static void main(String[] args) {
		int[] w = {1,4,3};//表示重量
		int[] val = {1500,3000,2000};//表示价值
		int m = 4;//背包最大值
		int n = val.length;//物品个数
		int[][] v = new int[n+1][m+1];//表示在前i个物品中能够装入容量为j的背包中的最大价值
		int[][] path = new int[n+1][m+1];//记录放入背包的物品
		for (int i = 1; i < v.length; i++) {
			for (int j = 1; j < v[0].length; j++) {
				//如果当前物品的重量大于背包的容量，则直接使用上一个单元格的装入策略
				if(w[i-1] > j){
					v[i][j] = v[i-1][j];
				}else {//当背包的容量大于当前装入物品的重量
					//拿上一单元格价值与   装入当前物品相价值+剩余空间可装入价值比较
					if(v[i-1][j] < val[i-1]+v[i-1][j-w[i-1]]){
						v[i][j] = val[i-1]+v[i-1][j-w[i-1]];
						path[i][j] = 1;
					}else{
						v[i][j] = v[i-1][j];
					}
				}
			}
		}
		//输出商品的价值情况
		for (int[] i:v) {
			System.out.println(Arrays.toString(i));
		}
		//输出商品的装入情况
		int i = path.length - 1; //行的最大下标
		int j = path[0].length - 1;  //列的最大下标
		//从path的最后开始找
		while(i > 0 && j > 0 ) { 
			if(path[i][j] == 1) {
				System.out.printf("第%d个商品放入到背包n", i); 
				j -= w[i-1]; 
			}
			i--;
		}
	}
}

	

关注数学，关注AI，关注我们公众号ID：Math-AI
数经典算法研究系列 之
 动态规划算法
基本概念
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
基本思想与策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。
在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)。
适用的情况
能采用动态规划求解的问题的一般要具有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;
}
END

	

算法——动态规划
 首先学习动态规划，我们要先知道什么是动态规划？
  算法导论这本书是这样介绍这个算法的，动态规划与分治方法类似，都是通过组合子问题的解来来求解原问题的。再来了解一下什么是分治方法，以及这两者之间的差别，分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。而动态规划与之相反，动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题(子问题的求解是递归进行的，将其划分为更小的子子问题)。在这种情况下，分治方法会做许多不必要的工作，他会反复求解那些公共子问题。而动态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。
定义:
  动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推(或者说分治)的方式去解决。
  动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
动态规划的应用场景：
动态规划方法一般用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望找到具有最优值的解，我们称这样的解为问题的一个最优解，而不是最优解，因为可能有多个解都达到最优值。

  我们解决动态规划问题一般分为四步：
1、定义一个状态，这是一个最优解的结构特征
2、进行状态递推，得到递推公式
3、进行初始化
4、返回结果
一般可以使用递归或者递推的写法来实现动态规划，这里以经典的求解斐波拉契数列为例子。如果没有学过动态规划，可能只会用递归的方式求解斐波拉契数列。代码如下：
long long fab(int n) {  //简单递归法if (n < 2) return 1;else return fab(n - 1) + fab(n - 2);}
事实上，这个递归会有很多重复的计算，以下递归树可以直观地表示。实际其时间复杂度为O(2n)，指数级的算法在数字稍大的时候基本不能用，更何况当问题规模较大时递归调用系统栈也是非常耗时的。
这里将动态规划的递归写法用简单递归的方法对比，比较当n=50时，两者所消耗的时间。
#include#include#includeusing namespace std;vector<long long> a; //存储计算结果 long long fab1(int n) {  //动态规划递归写法   if (n < 2) return 1; //递归边界  //以-1表示没有计算过   else if (a[n] == -1) a[n] = fab1(n - 1) + fab1(n - 2);  return a[n];}long long fab2(int n) {  //简单递归调用法  if (n < 2) return 1;  else return fab2(n - 1) + fab2(n - 2);}int main() {  clock_t start, end;  int n; cin >> n;  a.resize(n+1,-1);  long long result;  start = clock();  result= fab1(n);  end = clock();  cout << "动态规划递归算法运行时间：" << (end - start)*1.0 / CLOCKS_PER_SEC << "s" << endl;  cout << "运行结果：" << result << endl;  start = clock();  result = fab2(n);  end = clock();  cout << "直接递归算法运行时间：" << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;  cout << "运行结果：" << result;  return 0;}
  程序运行结果表示，动态规划递归算法的时间消耗几乎为0，而简单递归却用了一分多钟。这是因为把已经计算的结果记录下来，每次遇到需要计算已经计算的子问题时，直接使用上次计算过的结果，这样就把时间复杂度从O(2n)降到了O(n)。
经典例题——背包问题
题目描述：
假设山洞里共有a,b,c,d ,e这5件宝物(不是5种宝物)，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
首先要明确这张表是至底向上，从左到右生成的。
  为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。
  对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。
  同理，c2=0，b2=3,a2=6。
  对于承重为8的背包，a8=15,是怎么得出的呢？
  根据01背包的状态转换方程，需要考察两个值，
  一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；
在这里，
   f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
  f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量)，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
  f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6
由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包