本文共 1958 字，大约阅读时间需要 6 分钟。

什么是动态规划

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

动态规划的常见分类

编号动态规划：最大不下降子序列

划分动态规划：矩阵链乘、凸多边形三角剖分 数轴动态规划：0-1背包 前缀动态规划：最长公共子序列 树形动态规划：最优二分搜索树

或者

线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；

区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等； 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等； 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等

或者

计数：如选出k个数使得和是sum

求最大最小值：最大上升子序列 求存在性：博弈

算法原理

基本思想：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

使用条件：可分为多个相关子问题，子问题的解被重复使用

动态规划算法的设计步骤：

分析优化解的结构 递归地定义最优解的代价 自底向上地计算优化解的代价保存之，并获取构造最优解的信息 根据构造最优解的信息构造优化解

动态规划特点：

把原始问题划分成一系列子问题； 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间 自底向上地计算。 整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）

动态规划与分治法的区别：

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

1=例题Coin change

有银币面值2元，5元，7元无限，求最少的银币数量，刚好付清，如输入27，输出5（7+5+5+5+5）

（1）确定状态

最后一步： K枚银币面值总和是27 一定有最后的一枚硬币：a 前面总面额是27-a （我们不关心前面有多少种拼法） （27-a的硬币数量一定要最少）（最优策略） 子问题： 最少用多少枚硬币可以拼出27-a（规模更小） 如果a = 2， f（27） = f（27-2）+1 如果a = 5， f（27） = f（27-5）+1 如果a = 7， f（27） = f（27-7）+1 f（27） =min{f（25）+1，f（22）+1，f（20）+1} （2）转移方程 f【27】 =min{f【25】+1，f【22】+1，f【20】+1} （3）初始条件和边界情况 边界条件 Q1 x-2，x-5，x-7 小于0怎么办？ Q2 什么时候停下来？ Q3 拼不出来怎么办？ 返回正无穷 初始条件 f[0]=0 （4）计算顺序；从小到大 算法复杂度O（n*m）

#include 
   
    #include 
    
     //Coin change//有银币面值2元，5元，7元无限，求最少的银币，刚好付清，如输入27，输出5#define max 10000int min(int x,int y){	if(x>y) return y;	else return x;}int coinChange(int v[],int M){		int f[M+1];		f[0]=0;		for(int i = 1;i<= M;i++){			f[i] = max;			for(int j = 0;j<3;j++){				if(i>=v[j]&&f[i-v[j]]!=max){					f[i]= min(f[i-v[j]]+1,f[i]);				}			}		}		if(f[M]==max){			return -1;		}		return f[M];}int main(){	int m;	int v[3] = {2,5,7};	scanf("%d",&m);    printf("%d",coinChange(v,m));	return 0;}
    
   

转载地址：http://fgqen.baihongyu.com/