Dynamic Programming 动态规划概念简介

// Dynamic Programming 简称:DP

//动态规划 --要诀：状态
//概念：动态规划通常是用来解决最优化问题，这些问题可能存在多个解，每个
//解具有一个值我们希望找到一个具有最优值的解；
// 动态规划中我们主要关心的是找到一个最优解和求出最优解的值，而不是找出
//所有的最优解；

//动态规划的实质就是记忆话搜索
//特征：
//	能够分解为相互重叠的若干子问题,
//  	最优子结构：当问题的最优解包含了其子问题包含了其子问题的最优
//		解时，则，该问题具有最优子结构性质
//	满足最优性的原理；
//  重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不
//	总是新问题，有些子问题被反复计算多次；

// 动态规划算法的特点：
//		利用子问题的重叠性质，每一个子问题只解一次，而后将其解保存
//		在一个表格中，在以后尽可能多的利用这些子问题的解。                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      

//动态规划的算法一般分为三段：
// 1、分段：将原问题分解为若干个相互重叠的子问题
// 2、分析：分析问题是否满足最优性的原理，找出动态规划函数的递推式
// 3、求解：利用递推式自底向上计算，实现动态规划过程；

/*	分治法：将问题划分为一些独立的子问题，递归的求解各子问题，然后合并子问题的解；
 * 	动态规划：适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题
 * 
 * 	DP 算法的设计的设计步骤：
 * 		a、描述最优的结构
 * 		b、递归定义最优解的值
 * 		c、按自底而上的方式设计算最优解的值；
 * 		d、由计算出的结果创造一个最优解
 *	 
 */