动态规划
与贪心算法求局部最优解相比，动态规划求的是全局最优解（但不是每个问题都有最优解，比如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，单元格计算公式需要 具体问题具体分析 。
