动态规划
与贪心算法求局部最优解相比，动态规划求的是全局最优解（但不是每个问题都有最优解，比如NP完全问题就没有最优解）
例： 背包问题之动态规划解决
问题描述：
现在有一个背包可以装4磅物品，现手陵在要从商城里拿尽可能价值高的物品装进包里。
商城物品情况如下
每个动态规划都从一个网格（如下）开始
现在一行一行地填充该网格。
每个格子的计算公式：
填充吉他行 目前最大价值1500（吉他）
填充音箱：目前最大价值3000（音箱）
填充笔记本：目前最大价值3500（吉他+笔记本）
动态规划的原则就是将大问题拆解成多个小问题，先把小问题的最优解求出，再在考虑小问题最优解的前提下，得出最终问题的最优解
本例的背包问题中，先求出只有吉他一种物品时的最优解，再逐步添加物品，最终求出最优解
关于网格计算公式的补充：
整个动态规划求解过程中，是从小问题层逐步求解到大问题，自然每个格子要考虑的第一点就是前一格子的最大值，又，新的一层添加了新物品，所有也要考虑新物品的价值+剩余可用磅数的最大价值（上一层求得）
背包问题补充：
若再添加一个物品 ——项链{‘价值’：1000$，‘重量’：0.5磅}
此时敬薯拦如果沿用之前的网格
如果要装的物品为燕麦，木豆，大米 这种可以一部分一部分取出的物品
动态规划则解决不了这种情形，贪心可以。
旅游行程问题
当然我们可以用动态规划的网格法来亮胡得到一条最有价值的旅游路线
如果加入以下景点
在去巴黎的景点所花费的时间中，有0.5天是从伦敦前往巴黎的时间。
因此如果先去了埃菲尔铁塔,则去巴黎的剩下两个景点的花费时间也要减少2个小时
这种情况就不能使用之前的动态规划算法。
动态算法处理的每个子问题都是离散的
再来看一个案例
假如你要经营一个网站，网站主要任务是：英文单词翻译。即用户输入英文单词，你给出相应的翻译。 例用户输入fish，网站输出鱼
如果用户输入的hish，但词典中并没有该单词，此时应给出相似词。
怎么样才算是相似词呢？判断最大子串长度？
利用动态规划求出两字符串（fish和hish）的最大字串长度
动态规划解决问题总是要先知道网格中的各个元素：
两个坐标轴是什么？网格中的值是什么（通常为要 优化的指标 ）
1，分解问题：要求fish和hish的最大子串，可以先求其字串的最大公共子串（如先求fis和his）。考虑两个坐标轴为两个单词，则网格中的值为最大子串的长度。
接下来填充该网格。不断验证得到单元格公式：
单元格公式解释：
1）两字母相同，则局部最大字串要延长，即斜上方（cell[i][j]）的值加一(这里指标值在斜方向上累加)
2）若是不同，则局部最大字串为0
两字符串的最大字串长度即为网格中的最大值3。
如果用户输入fosh，那么要返回fish还是fort呢？
如果判断依据为最大子串，则会返回fort，但实际上fish和fosh更像！
因此我们考虑判断依据为两字符串的最大公共子序列长度（即两字符串公共字符的个数）
求最大公共子序列的单元格公式为：
fosh和fort的最大公共子序列长度为2
fosh和fish的最大公共子序列长度为3
此时就可以返回正确结果fish而非fort。
1，动态规划通常用于解决 在给定约束条件下优化某个指标值
2，动态规划的原则就是：将大问题分解成小问题，在解决了小问题的条件下，逐步求解大问题。（一个分解问题的方法就是，将条件逐渐减少，从最简单的情况开始分析）
3，动态规划使用的一个必要条件为： 分解出来的每个小问题都是离散的
4，每种动态规划方案都设计网格
4.1，网格的每个格子都是一个小问题
4.2，网格的每个格子的值都是指标的值
4.3，单元格计算公式需要 具体问题具体分析 。
