标签（空格分隔）： 简单算法 笔记 python
动态规划
动态规划原理是先解决子问题，再逐步解决大问题。
简单例子（背包问题）：你是小偷，现有一个容量为4磅的背包。商店有三种商品为：$3000的音响重为4磅；$2000的笔记本电脑重为3磅，$1500的吉他重为1磅。你怎样偷窃才能获利最多？
最简单的办法：遍历所有可能组合，找到最值钱的组合。可惜存在一个巨大的缺点，算法运行时间为O(2^n),慢如蜗牛。
合理的方法（动态归划）：原理是先解决小背包（子背包）问题，再逐步解决原来的问题。通过迭代当前容量最大价值解决问题，如下图：
局限：但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。举例，有限时间在英国各地游览和中途去法国各景点游览。
启示：
- 动态规划可帮助你在给定约束条件下找到最优解。在背包问题中，你必 须在背包容量给定的情况下，偷到价值最高的商品。
在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
每种动态规划解决方案都涉及网格。
单元格中的值通常就是你要优化的值。在前面的背包问题中，单元格的值为商品的价值。
每个单元格都是一个子问题，因此你应考虑如何将问题分成子问题，这有助于你找出网格的坐标轴。
最长公共子串
当你不小心hish，输入法怎样会提供相近的单词fish作为参考，而不是vista？这是就要计算最长公共子串(是网格中最大的数字)，如下图：
由此，输入法判断的是fish作为参考。
具体代码实现，以后再补充。
最长公共子序列
假设你不小心输入了fosh，原本想输入的是fish还是fort呢?
可以看出，两个单词和fosh的最长公共子串都为2，这是就要判断最长公共子序列，计算公式如下图：
所以输入法判断想输入的是fish。
具体代码，以后补充。
小结
