动态规划（Dynamic programming，简称DP）

[wangyingjun]

动态规划（Dynamic programming，简称DP）

动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划和递归都是解决通过子问题来解决最终问题的方法。它们之间区别是递归通常情况下计算会有重复计算，而动态规划把每次的解都存储下来，是用空间换时间的方法。

1. 递归方案
   2^n 时间复杂度

2. 动态规划
   n^2 时间复杂度

背包问题（Knapsack problem）

背包问题(Knapsack problem)是在1978年提出的，它都可以类似的描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

例子：分别有3种物品，A:质量4kg,价值30；B:质量3KG,价值20；C:质量1KG,价值15；有一个容量为4KG的背包，如何装下价值最高的物品？

/*
 * 0-1背包问题，背包的容量长度为i，物品的种类为j，则最优解为 d[i][j]
 * 分析 计算第j种物品时，分为 放入和不放入
 * 	不放入的情况：最大价值为 d[i][j-1] 时的最大价值
 *	放入的情况：	最大价值为 当前物品价值 + d[i-当前物品重量][j-1] (剩余物品下和剩余背包下的最大价值)
 *	取max(不放入情况，放入情况)
 */

字符串相似度，最长公共子串

/*
 * 公共字串问题，比较两个字符串的最长公共字串，鉴别两个字符串的相似度
 * 字符串a的长度为i，字符串b的长度为j，最长公共字串的最优解为 d[i][j]
 * 分析： 
 * 	如果 a[i] 和 b[j] 相等： 则 d[i-1][j-1] + 1
 * 	如果 b[i] 和 b[j] 不相等： 则 max(d[i][j-1], d[i-1][j])
 *	取 max(相等，不相等)
 */

编辑距离

查看这篇